LeetCode 题解工作台
使数组按非递减顺序排列
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 。 重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。 示例 1： 输入： nums = [5,3,4,4,7,3,6,11,…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
class Solution: def totalSteps(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。
示例 1：
输入：nums = [5,3,4,4,7,3,6,11,8,5,11] 输出：3 解释：执行下述几个步骤： - 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11] - 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11] - 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11] [5,7,11,11] 是一个非递减数组，因此，返回 3 。
示例 2：
输入：nums = [4,5,7,7,13] 输出：0 解释：nums 已经是一个非递减数组，因此，返回 0 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109
解题思路
方法一：单调栈
class Solution:
def totalSteps(self, nums: List[int]) -> int:
stk = []
ans, n = 0, len(nums)
dp = [0] * n
for i in range(n - 1, -1, -1):
while stk and nums[i] > nums[stk[-1]]:
dp[i] = max(dp[i] + 1, dp[stk.pop()])
stk.append(i)
return max(dp)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n) for optimized monotonic stack or linked-list pointer approaches to O(n^2) for naive iteration. Space complexity is O(n) for stack or linked-list representations. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an efficient way to detect elements violating non-decreasing order without full array scans.
- question_mark
Expect the candidate to connect array behavior to linked-list pointer updates or stack levels.
- question_mark
Notice if candidate handles edge cases like already non-decreasing arrays or single-element arrays.
常见陷阱
外企场景- error
Removing elements directly from the array without considering index shifts can lead to wrong results.
- error
Failing to count steps correctly when multiple elements are removed in one pass.
- error
Ignoring the need for repeated passes until the array stabilizes as non-decreasing.
进阶变体
外企场景- arrow_right_alt
Instead of deleting elements, return the minimum number of increment operations needed to achieve non-decreasing order.
- arrow_right_alt
Apply the same removal rules but on a circular array where the last element compares to the first.
- arrow_right_alt
Track positions of removed elements per step to optimize subsequent operations for large arrays.