LeetCode 题解工作台
零数组变换 III
给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [l i , r i ] 。 每一个 queries[i] 表示对于 nums 的以下操作： 将 nums 中下标在范围 [l i , r i ] 之间的每一个元素 最多 减少 1 。 坐标范…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们希望尽可能多地「移除」区间查询，但又要保证对每个位置 来说，被选中、覆盖到它的查询次数 至少达到原数组值 ，这样才能把该位置的值“减”到 0 或以下。如果对于某个位置 无法满足 ，就说明再多选任何查询都不可能让该位置归零，返回 。 为了做到这一点，我们按查询区间的左端点从小到大遍历，并维护：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [li, ri] 。
每一个 queries[i] 表示对于 nums 的以下操作：
- 将
nums中下标在范围[li, ri]之间的每一个元素 最多 减少 1 。 - 坐标范围内每一个元素减少的值相互 独立 。
零数组 指的是一个数组里所有元素都等于 0 。
请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组 。如果无法将 nums 变为一个 零数组 ，返回 -1 。
示例 1：
输入：nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
输出：1
解释：
删除 queries[2] 后，nums 仍然可以变为零数组。
- 对于
queries[0]，将nums[0]和nums[2]减少 1 ，将nums[1]减少 0 。 - 对于
queries[1]，将nums[0]和nums[2]减少 1 ，将nums[1]减少 0 。
示例 2：
输入：nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
输出：2
解释：
可以删除 queries[2] 和 queries[3] 。
示例 3：
输入：nums = [1,2,3,4], queries = [[0,3]]
输出：-1
解释：
nums 无法通过 queries 变成零数组。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= li <= ri < nums.length
解题思路
方法一：贪心 + 差分数组 + 优先队列
我们希望尽可能多地「移除」区间查询，但又要保证对每个位置 来说，被选中、覆盖到它的查询次数 至少达到原数组值 ，这样才能把该位置的值“减”到 0 或以下。如果对于某个位置 无法满足 ，就说明再多选任何查询都不可能让该位置归零，返回 。
为了做到这一点，我们按查询区间的左端点从小到大遍历，并维护：
- 差分数组
d：用于记录当前已应用的查询在何处分界——当我们在区间 上“应用”一次查询时，立刻在差分数组位置d[l] += 1，并在d[r+1] -= 1，这样在遍历到下标 时累加前缀和就能知道有多少次查询覆盖了 。 - 最大堆
pq：存放当前「候选」区间查询的右端点（取负数以便 Python 最小堆模拟最大堆）。为什么选「最晚结束」的区间？因为它能覆盖更远的位置，我们的贪心策略是：在每个 处，只在必要时才摘取堆顶最长的区间来增加一次覆盖，这样能为后续位置保留更多可用的区间。
具体步骤如下：
-
先对
queries按左端点l升序排序； -
初始化差分数组
d长度为n+1（用来处理r+1处的减操作），以及当前覆盖次数s=0、堆指针j=0； -
从 遍历到 ：
-
先把
d[i]累加到s，即时更新已有的覆盖次数； -
将所有左端点 的查询 压入最大堆
pq（存-r），并推进j； -
当当前覆盖次数
s小于所需值nums[i]，且堆不空且堆顶区间仍能覆盖 （即 ）时：- 弹出堆顶（最长的区间），等价于“应用”这次查询；
- 令
s += 1并在d[r+1] -= 1（使得在跨过r后覆盖次数自动回退）；
-
重复上述步骤，直到
s>=nums[i]或无法再选区间； -
若此时
s<nums[i]，说明无法将位置 归零，直接返回 。
-
-
全部遍历完毕后，剩在堆里的区间都是「未被弹出」的，也就是真正被保留（即未被用来完成“归零”任务）的查询。堆大小即为答案。
时间复杂度 ，空间复杂度 ，其中 是数组的长度，而 是查询的个数。
class Solution:
def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
queries.sort()
pq = []
d = [0] * (len(nums) + 1)
s = j = 0
for i, x in enumerate(nums):
s += d[i]
while j < len(queries) and queries[j][0] <= i:
heappush(pq, -queries[j][1])
j += 1
while s < x and pq and -pq[0] >= i:
s += 1
d[-heappop(pq) + 1] -= 1
if s < x:
return -1
return len(pq)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m \times \log{m}) due to sorting m queries and computing prefix sums over n elements. Space complexity is O(n + m) for the prefix sum array and storing sorted queries. |
| 空间 | O(n + m) |
面试官常问的追问
外企场景- question_mark
Pay attention if a candidate sorts queries to apply the greedy choice efficiently.
- question_mark
Watch for correct prefix sum usage to track cumulative operations on nums.
- question_mark
Check if the candidate validates the zero array invariant at each step.
常见陷阱
外企场景- error
Failing to sort queries before applying the greedy removal can lead to incorrect minimal removal.
- error
Neglecting prefix sum updates after removing a query may break invariant checks.
- error
Returning a valid index without fully confirming nums becomes zero after all remaining queries.
进阶变体
外企场景- arrow_right_alt
Allow queries to both increment and decrement, requiring signed prefix sums.
- arrow_right_alt
Optimize for very large n with sparse queries using segment trees instead of full prefix sums.
- arrow_right_alt
Find the maximal number of removable queries while still achieving a zero array.