点击获取AI摘要

3362. 零数组变换 III M

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [lᵢ, rᵢ] 。

每一个 queries[i] 表示对于 nums 的以下操作：

将 nums 中下标在范围 [lᵢ, rᵢ] 之间的每一个元素最多减少 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 <= 10⁵
0 <= nums[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= lᵢ <= rᵢ < nums.length

问题分析

给定一个长度为 $n$ 的整数数组 nums 和一个包含 $m$ 个查询的二维数组 queries，其中 queries[i] = [l_i, r_i] 表示对于 nums 执行一次操作：将下标在范围 $[l_i, r_i]$ 之间的每个元素最多减少 $1$ （各位置减少值相互独立）。目标是从原来的 $m$ 个查询中删除尽可能多的查询，使得剩余查询仍能将 nums 变成全 0 的“零数组”。如果无论如何也不能变成零数组，则返回 $-1$ 。

关键在于，“每次操作对区间内元素各自减少最多 1” 意味着，若某位置 $i$ 在剩余操作中被覆盖了 $k_i$ 次，则该位置至多减少 $k_i$ ，要达到最终 nums[i] = 0，就需要

$k_i \;\ge\; \text{nums}[i]\,,\quad \forall\,0 \le i < n.$

此处每个查询只有两种选择：保留或删除。若保留，就会对它覆盖区间内的各个位置“增加 $1$ ”的覆盖次数；若删除，就相当于完全忽略它对覆盖次数的贡献。我们需要在确保对每个 $i$ ，剩余查询的覆盖次数 $\sum 1\{i \in [l_j, r_j]\}$ 至少等于 $\text{nums}[i]$ 的前提下，尽量删除也就是丢弃尽量多的区间。

换言之，若最少要保留 $K$ 条区间才能覆盖所有位置的需求，那么最多能删除 $m-K$ 条。若任何选择都无法满足某位置覆盖次数需求，则返回 $-1$ 。

算法思路

本文展示两种思路的实现代码，逻辑不同，但都遵循“贪心地选最需要的区间以满足每个位置的覆盖需求”这一核心原则。

方法一：按左端点分桶 + 差分数组 + 贪心选右端最大的可用区间

按左端点分桶
- 事先将所有查询 [l, r] 按其左端点 $l$ 归类：用 start_at[l] 存储所有左端为 $l$ 的查询的右端 $r$ 。这样在扫描数组位置 $i$ 时，可以将所有新“激活”的区间（左端恰好是 $i$ ）一次性加入到可选集合里。
差分数组维护“已选区间覆盖次数”
- 用一个长度为 $n+1$ $n + 1$ 的差分数组 $\mathrm{diffCover}$ $diffCover$ ，配合一个变量 $\mathrm{currCover}$ $currCover$ 来维护“当前已保留的区间对当前位置 $i$ $i$ 的覆盖次数”。矩阵含义如下：
  - 当我们决定保留某个区间 $[l, r]$ 时，就执行
    $\mathrm{diffCover}[l] \;+=\; 1,\qquad \mathrm{diffCover}[r+1] \;-\!=\;1,$
    这样在后续扫描时，位置 $p$ 所被选中区间覆盖次数 $\mathrm{currCover}(p)$ 可以通过累加前缀和来得到。
  - 在扫描到位置 $i$ 时，先用
    $\mathrm{currCover} \;=\; \sum_{j=0}^{i-1} \mathrm{diffCover}[j]$
    （代码中累加 $\mathrm{diffCover}[i]$ 到 $\mathrm{currCover}$ ）以得到“已保留区间对 $i$ 的覆盖次数”。如果 $\mathrm{currCover} < \mathrm{nums}[i]$ ，说明还需多选区间来满足位置 $i$ 的需求。
维护可选区间按右端最大化
- 用 availCount[r] 统计当前“可选且未选”且右端恰好为 $r$ 的区间数量；用 intervals_by_r[r] 存储这些区间的左端 $l$ 。
- 同时维护一个指针 maxR，表示当前所有可选区间中最大的右端。当我们要为当前位置 $i$ 额外“补覆盖”时，总是“贪心”地优先选取右端最大的区间（因为它能为之后尽可能多的位置提供覆盖机会），即不断从 r = maxR 的组里弹出一条区间 [l_{\text{top}},\,\maxR] 来保留。
- 每当保留一条 [l_{\text{top}},\,\maxR]，我们会：
  - availCount[maxR] -= 1
  - chosenCount += 1（记录已选区间数）
  - 更新差分：diffCover[l_top] += 1, diffCover[maxR+1] -= 1，并即时 currCover += 1 因为该区间确实覆盖了当前 $i$ 。
- 如果 availCount[maxR] 变为 0，则将 maxR 不断向左移动至下一个 availCount[r'] > 0 为止（且保持 $r' \ge i$ ），否则就说明没有可选区间能覆盖 $i$ ，直接返回 $-1$ 。
逐位扫描
- 从 $i=0$ 到 $i=n-1$ ，先累加 diffCover[i] 到 currCover，再将左端恰好是 $i$ 的所有区间“激活”到 availCount 和 intervals_by_r，更新 maxR。
- 如果此时 currCover < nums[i]，就在当前可选中右端最大的 maxR 里不断选区间来增加覆盖，直到 currCover >= nums[i] 或者发现无法满足而返回 $-1$ 。
- 这样保证每个位置都至少被覆盖 nums[i] 次。扫描结束后，若没有失败，则记录已保留区间数 $K = \mathrm{chosenCount}$ ，答案即 $m - K$ 。
数学公式
- 差分数组更新公式：
  $\mathrm{diffCover}[l] \;+=\;1,\quad \mathrm{diffCover}[r+1]\;-\!=\;1\,.$
- 在扫描到位置 $i$ 时，已选区间的覆盖次数：
  $\mathrm{currCover}(i) \;=\; \sum_{j=0}^i \mathrm{diffCover}[j]\,.$
- 需要满足：
  $\mathrm{currCover}(i) \;\ge\; \mathrm{nums}[i],\quad \forall\,i.$

方法二：按左端排序 + 最大堆 + 差分前缀

将查询按左端 $l$ 升序排序
- 令 queries.sort(key=lambda x: x[0])，并用指针 j 遍历所有查询。当扫描到数组位置 $i$ 时，顺便把所有 $l \le i$ 的区间逐一推入堆中。
用最大堆维护“已激活的区间按右端降序”
- 在Python里，我们用 heapq，但由于它是最小堆，我们将右端 $r` 取负数存入堆，实际效果是“堆顶”对应最大的 $r$ 。
- 当扫描到 $i$ ，先将左端 $\le i$ 的所有区间都 heappush(h, -r)。
差分数组 diff 记录“当前已选区间对后续位置的累积覆盖影响”
- 初始化 diff = [0]*(n+1)，并维护一个前缀和 sum_d = 0。含义是：sum_d = \sum_{k=0}^{i-1} diff[k]。
- 当我们保留一条区间 $[l, r]$ 时，执行：
  $\mathrm{diff}[\,r+1\,] \;+\!=\; -1\quad(\text{因为 pos $>r$ 时覆盖计数会减少})$
  并且在选区间时，立刻做 sum_d -= 1 并计入已选区间计数 k += 1，相当于该区间“直接覆盖了当前 $i$ ”，所以对 $i$ 之后的所有位置在 sum_d 上预先扣了 1。总之，这里将覆盖量通过一维差分转换成后缀影响。
遍历数组
- 对于每个 $i$ $i$ ，先做 sum_d += diff[i]。此时 sum_d 代表“由之前保留的区间，在当前位置及其之后还能继续贡献的覆盖次数”与当前位置应有的需求 -nums[i] 做对比：
  - 因为我们维持 sum_d 是负数时表示对当前位置仍需额外 $(-sum_d)$ 的“补覆盖”。
- 如果 sum_d <= -nums[i]，说明当前已有保留区间的覆盖就足够满足 nums[i]，不需要额外选。
- 否则，就不断从堆中弹出右端最大的区间（即 -heap[0] 最大），若弹出区间的右端 $r` $\ge i$ $\geq i$ ，就保留它：
  - 执行 diff[r+1] += 1（意味着在位置 $r+1$ 开始，“覆盖贡献”减少 1），
  - sum_d -= 1，k += 1。
- 重复弹区间直到 sum_d <= -nums[i] 或堆空或堆顶区间右端 $< i$ （此时堆里所有剩余区间都无法覆盖当前 $i$ ，直接返回 $-1$ ）。
- 如果循环结束后仍然 sum_d > -nums[i]，说明无法达到需求，返回 $-1$ 。
答案
- 如果整个 $i=0..n-1$ 都顺利通过，记录保留的区间数 $K = k$ ，则最多能删除 $m - K$ 。

时间复杂度

方法一
- 构建 start_at 要 $O(m)$ ，差分数组大小 $O(n)$ 。
- 遍历每个位置 $i$ $i$ 时：
  - 将左端恰为 $i$ 的区间激活到 availCount 和 intervals_by_r，总共需要把 $m$ 条区间分配一次，属于 $O(m)$ 。
  - 在最坏情况下，每个位置都可能进行一次或多次“选区间”操作，总共最多选 $K$ 条区间， $K \le m$ ，每次更新差分和 maxR 都是 $O(1)$ 或者 maxR 左移 $O(1)$ 次的摊销。
- 因此总体时间复杂度 $O(n + m)$ 。
方法二
- 先对查询排序 $O(m\log m)$ 。
- 遍历 $0..n-1$ $0.. n - 1$ ，每步：
  - 把左端 $\le i$ 的查询压入堆，所有 $m$ 条均只入一次堆，总共 $O(m\log m)$ 。
  - 弹堆操作最多也是 $O(m\log m)$ 。
  - 差分数组前缀 $sum_d$ 的累加是 $O(1)$ 。
- 因此总复杂度 $O(m\log m + n)$ 。若 $m$ 远大于 $n$ ，则主要开销在堆操作上。

代码分解

方法一

构建 start_at 列表

1
2
3

start_at = [[] for _ in range(n)]
for idx, (l, r) in enumerate(queries):
    start_at[l].append(r)

意味着 start_at[i] 内存储所有左端为 $i$ 的查询的右端 r。

初始化辅助数组和变量

diffCover = [0] * (n + 1)   # 差分数组
currCover = 0              # 前缀和，表示当前位置已有覆盖
chosenCount = 0            # 已保留区间数
availCount = [0] * n       # 右端为 r 的“可选未选”区间数量
intervals_by_r = [[] for _ in range(n)]  # 记录右端 r 下的各左端 l
maxR = n - 1               # 当前可选区间的最大右端

从 i=0…n-1 扫描

累加差分：currCover += diffCover[i]。

将所有 l=i 的区间激活：

for r in start_at[i]:
    availCount[r] += 1
    intervals_by_r[r].append(i)
    if r > maxR: maxR = r

“剔除过期”并维护 maxR >= i && availCount[maxR] > 0。

若 currCover < nums[i]，就要补选区间：

while currCover < nums[i]:
    if maxR < i: return -1
    # 取出右端 = maxR 的一个可选区间
    l_top = intervals_by_r[maxR].pop()
    availCount[maxR] -= 1
    chosenCount += 1
    currCover += 1
    diffCover[l_top] += 1
    diffCover[maxR + 1] -= 1
    if availCount[maxR] == 0:
        # maxR 不断左移
        while maxR >= i and (availCount[maxR] == 0):
            maxR -= 1

若循环结束时 currCover >= nums[i]，位置 $i$ 满足需求，继续下一个 $i+1$ 。

返回结果
- 如果遍历结束都没出错，最少要保留 chosenCount 条，最多可删除 m - chosenCount。否则中途返回 -1。

方法二

排序与初始化
1
2
3
4
5
queries.sort(key=lambda x: x[0])
h = []
diff = [0] * (len(nums) + 1)
q, j = len(queries), 0
k = sum_d = 0
- h 为堆（Python 默认最小堆，用 -r 保存便于每次弹出最大右端）。
- diff[i] 存储差分：一旦保留区间 $[l,r]$ ，就对 diff[r+1] += 1 来表示“从 $r+1$ 开始，后缀不再被此区间覆盖”。
- sum_d 追踪前 $i$ 的差分前缀和。

遍历 nums

for i, x in enumerate(nums):
    sum_d += diff[i]
    # 如果已有覆盖 sum_d <= -x，说明已满足 nums[i]
    if sum_d <= -x:
        continue
    # 否则，把左端 <= i 的所有区间压堆
    while j < q and queries[j][0] <= i:
        heapq.heappush(h, -queries[j][1])
        j += 1
    # 弹堆，补选最大的右端区间
    while sum_d > -x and h and -h[0] >= i:
        r = -heapq.heappop(h)
        diff[r + 1] += 1
        sum_d -= 1
        k += 1
    # 若无法满足需求，则失败
    if sum_d > -x:
        return -1
return q - k

对每个位置 $i$ ，先 sum_d += diff[i]。此时若 sum_d <= -nums[i]，说明此前已选的区间覆盖次数充足；否则进入补选。
在补选阶段，只要当前 sum_d > -nums[i]，且堆顶区间的右端 $r \ge i$ ，就可以选取它：sum_d -= 1 立刻反映“当前 $i$ 被此区间覆盖”；diff[r+1] += 1 表示“在 $r+1$ 处去掉这条区间后续的覆盖贡献”。
若在此之后仍不能满足，则直接返回 -1。

代码实现

from typing import List

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        n, m = len(nums), len(queries)
        # 1. 把所有区间按左端点 l 分桶
        #    start_at[i] 里存的，是所有左端点恰好为 i 的查询 (r)
        start_at = [[] for _ in range(n)]
        for idx, (l, r) in enumerate(queries):
            start_at[l].append(r)

        # 2. 差分数组 diffCover 用于维护“已选区间到当前位置 i 的覆盖次数”
        diffCover = [0] * (n + 1)
        currCover = 0    # 当前在 i 处，已选的区间一共覆盖了多少次
        chosenCount = 0  # 已经保留（选中）的区间数

        # 3. availCount[r] 统计：目前“可选”且尚未被选的“右端点恰好等于 r”的区间有多少条
        availCount = [0] * n
        # intervals_by_r[r] 存储：当区间 [l,r] 一被激活，就把它的 l push 到这里
        intervals_by_r = [[] for _ in range(n)]

        # 4. 用一个指针 maxR 来指向“当前可选区间里最大的 r”
        maxR = n - 1

        # 5. 从 i=0..n-1 依次扫描
        for i in range(n):
            # ——(A) 先把 diffCover[i] 累到 currCover 上
            currCover += diffCover[i]

            # ——(B) 把左端点 l = i 的区间全部“激活”
            for r in start_at[i]:
                availCount[r] += 1
                intervals_by_r[r].append(i)
                if r > maxR:
                    maxR = r

            # ——(C) 剔除过期的 r：保证 maxR ≥ i 且 availCount[maxR] > 0
            while maxR >= i and (availCount[maxR] == 0):
                maxR -= 1

            # ——(D) 如果 currCover < nums[i]，就必须“贪心地”从 r = maxR 开始选区间补覆盖
            while currCover < nums[i]:
                if maxR < i:
                    return -1

                # 从 intervals_by_r[maxR] 中 pop 出一个左端 l_top
                l_top = intervals_by_r[maxR].pop()
                availCount[maxR] -= 1
                chosenCount += 1
                # 该区间覆盖了当前 i，立刻补一个 currCover
                currCover += 1

                # 差分更新：对 [l_top, maxR] 内所有位置各 +1
                diffCover[l_top] += 1
                if maxR + 1 < len(diffCover):
                    diffCover[maxR + 1] -= 1

                # 如果 maxR 组里已无可选区间，继续将 maxR 左移
                while maxR >= i and (availCount[maxR] == 0):
                    maxR -= 1

            # 至此 currCover ≥ nums[i]，安全进入 i+1

        # 扫完所有 i，没有失败
        return m - chosenCount

二

import heapq

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        # 将 queries 按左端升序排序
        queries.sort(key=lambda x: x[0])
        h = []  # 最大堆（用负的 r 存储）
        diff = [0] * (len(nums) + 1)
        q, j = len(queries), 0
        k = sum_d = 0

        for i, x in enumerate(nums):
            # 更新前缀和
            sum_d += diff[i]
            # 如果已有 sum_d <= -x，则说明已满足 nums[i]，继续
            if sum_d <= -x:
                continue

            # 将左端 <= i 的所有查询压入堆
            while j < q and queries[j][0] <= i:
                heapq.heappush(h, -queries[j][1])
                j += 1

            # 弹堆补选右端最大的区间，直到满足需求或堆空/无法覆盖
            while sum_d > -x and h and -h[0] >= i:
                r = -heapq.heappop(h)
                # 差分更新，位置 r+1 开始对后缀去掉一个覆盖
                diff[r + 1] += 1
                sum_d -= 1
                k += 1

            # 如果仍然不够覆盖，返回 -1
            if sum_d > -x:
                return -1

        # 能完成覆盖，最多删除 q - k
        return q - k