LeetCode 题解工作台
将所有元素变为 0 的最少操作次数
给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。 在一次操作中，你可以选择一个子数组 [i, j] （其中 0 ），将该子数组中所有 最小的非负整数 的设为 0。 返回使整个数组变为 0 所需的 最少 操作次数。 一…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
根据题意，我们应该把数字中最小的数先变成 ，再把次小的数变成 ，依此类推。在这里过程中，如果两个数之间有更小的数隔开，那么它们需要额外的一次操作才能变成 。 我们可以维护一个从栈底到栈顶单调递增的栈 ，遍历数组 中的每个数 ：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。
在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。
返回使整个数组变为 0 所需的最少操作次数。
一个 子数组 是数组中的一段连续元素。
示例 1：
输入: nums = [0,2]
输出: 1
解释:
- 选择子数组
[1,1]（即[2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为[0,0]。 - 因此，所需的最少操作次数为 1。
示例 2：
输入: nums = [3,1,2,1]
输出: 3
解释:
- 选择子数组
[1,3]（即[1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为[3,0,2,0]。 - 选择子数组
[2,2]（即[2]），将 2 设为 0，结果为[3,0,0,0]。 - 选择子数组
[0,0]（即[3]），将 3 设为 0，结果为[0,0,0,0]。 - 因此，最少操作次数为 3。
示例 3：
输入: nums = [1,2,1,2,1,2]
输出: 4
解释:
- 选择子数组
[0,5]（即[1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为[0,2,0,2,0,2]。 - 选择子数组
[1,1]（即[2]），将 2 设为 0，结果为[0,0,0,2,0,2]。 - 选择子数组
[3,3]（即[2]），将 2 设为 0，结果为[0,0,0,0,0,2]。 - 选择子数组
[5,5]（即[2]），将 2 设为 0，结果为[0,0,0,0,0,0]。 - 因此，最少操作次数为 4。
提示:
1 <= n == nums.length <= 1050 <= nums[i] <= 105
解题思路
方法一：单调栈
根据题意，我们应该把数字中最小的数先变成 ，再把次小的数变成 ，依此类推。在这里过程中，如果两个数之间有更小的数隔开，那么它们需要额外的一次操作才能变成 。
我们可以维护一个从栈底到栈顶单调递增的栈 ，遍历数组 中的每个数 ：
- 当栈顶元素大于 时，说明 将栈顶元素隔开了，我们需要把栈顶元素弹出，并将答案加 ，直到栈顶元素不大于 为止。
- 如果 不为 ，且栈为空或者栈顶元素不等于 ，则将 入栈。
遍历结束后，栈中剩余的元素都需要额外的一次操作才能变成 ，因此我们将答案加上栈的大小即可。
时间复杂度 ，空间复杂度 ，其中 是数组 的长度。
class Solution:
def minOperations(self, nums: List[int]) -> int:
stk = []
ans = 0
for x in nums:
while stk and stk[-1] > x:
ans += 1
stk.pop()
if x and (not stk or stk[-1] != x):
stk.append(x)
ans += len(stk)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on iterating through unique values and processing their positions, roughly O(n log n) for sorting plus O(n) scanning. Space complexity is O(n) for storing index mappings in a hash table. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on efficiently finding the minimum in subarrays without repeated full scans.
- question_mark
Consider hash maps to quickly locate element positions instead of naive iteration.
- question_mark
Stack or monotonic scanning patterns hint at reducing overlapping operation counts.
常见陷阱
外企场景- error
Failing to process elements in ascending order can increase operation count unnecessarily.
- error
Neglecting contiguous blocks leads to redundant subarray operations.
- error
Using repeated full scans instead of index maps causes timeouts for large arrays.
进阶变体
外企场景- arrow_right_alt
Change operation to set maximum instead of minimum, requiring reverse processing.
- arrow_right_alt
Limit subarray length, forcing more careful selection and increased operations.
- arrow_right_alt
Allow decrement by one instead of full zeroing, increasing scan complexity.