点击获取AI摘要

3355. 零数组变换 I M

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个查询 queries[i]：

在 nums 的下标范围 [li, ri] 内选择一个下标子集。
将选中的每个下标对应的元素值减 1。

零数组 是指所有元素都等于 0 的数组。

如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。

示例 1：

输入： nums = [1,0,1], queries = [[0,2]]

输出： true

解释：

对于 i = 0：

选择下标子集 [0, 2] 并将这些下标处的值减 1。

数组将变为 [0, 0, 0]，这是一个零数组。

示例 2：

输入： nums = [4,3,2,1], queries = [[1,3],[0,2]]

输出： false

解释：

对于 i = 0：

选择下标子集 [1, 2, 3] 并将这些下标处的值减 1。

数组将变为 [4, 2, 1, 0]。

对于 i = 1：

选择下标子集 [0, 1, 2] 并将这些下标处的值减 1。

数组将变为 [3, 1, 0, 0]，这不是一个零数组。

提示：

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[i] = [l_i, r_i]。对于每个查询，我们可以在区间 [l_i, r_i] 内任意选取一些下标，将这些位置对应的元素减 1。要在“按顺序”处理完所有 m 个查询之后，将原始数组 nums 变成“零数组”（即所有元素都恰好被减为 0），需要满足：

对于每个位置 j，它最终被减去的次数必须恰好等于 nums[j]。
而每次查询只能在它指定的区间内对某个位置减 1，并且每个查询对同一个位置最多减 1 次。

算法思路

设 cover[j] 表示有多少个查询区间 [l_i, r_i] 覆盖位置 j。

如果 cover[j] < nums[j]，那么位置 j 即使在所有能覆盖它的查询中都“选中”它去减 1，最大也只能被减 cover[j] 次，仍然无法将 nums[j] 减到 0，直接返回 false。

如果对每个 j 都满足 cover[j] >= nums[j]，理论上我们可以在所有覆盖 j 的查询中选取任意 nums[j] 次去对 j 减 1。由于不同位置的选择互不干扰（每次查询可以对区间内任意多个下标同时减 1，没有上限），只要每个位置都有足够的“机会”被减，就能找到一种方案使得最终所有位置正好被减到 0。

考虑“按顺序”执行查询的限制：即使我们在前面的查询选择了“跳过”某些位置，只要剩下“未来的查询”依然足够覆盖剩余需要减的次数字段，就没问题。实际上，只需满足总体上 cover[j] >= nums[j] 即可，因为可以把对于每个 j 的 nums[j] 次减操作安排在它被覆盖的最后 nums[j] 个查询上。

先用一个差分数组（长度 n+1）来累积每个查询对各下标的覆盖次数：

diff = new int[n+1];
对于每个 query = [l, r]:
    diff[l] += 1;
    diff[r+1] -= 1;    // 若 r+1 越界则跳过
再对 diff 做前缀和，得到 cover[0…n-1]。

这样就能在 $O(n + m)$ 的时间内算出 cover[j] = 该下标被多少查询覆盖。
遍历 j=0…n-1，若发现 cover[j] < nums[j]，立即返回 false。
如果所有 j 都通过检查，则返回 true。

时间复杂度

差分数组初始化及累计： $O(m)$
计算前缀和： $O(n)$
最终逐位检查： $O(n)$
整体为 $O(n + m)$ ，空间复杂度 $O(n)$ （存储 diff/cover）。
使用了长度为 n+1 的差分数组 diff，以及长度为 n 的覆盖次数数组 cover，总计 $O(n)$ 额外空间。

代码分解

差分数组 diff 在索引 l 处 +1、在 r+1 处 −1，最终对 diff 做前缀和就相当于：每个查询在 [l, r] 区间内为 cover[j] 累加了 1。
得到的 cover[j] 就是“有多少个查询区间覆盖位置 j”。
对于位置 j 来说，如果总共被覆盖的次数少于它当前需要减的次数 nums[j]，无论怎么选都不够，将来无法把它减到 0；否则只要“用掉”它需要的 nums[j] 次就行。
由于不同下标在同一次查询中是否选取互不干扰（每次查询可以对区间里任意子集进行减操作），所以只用全局判断 cover[j] >= nums[j] 即可。

代码实现

class Solution:
    def isZeroArray(self, nums: list[int], queries: list[list[int]]) -> bool:
        n = len(nums)
        m = len(queries)

        # 1. 构造差分数组 diff，长度为 n+1，初始全 0
        diff = [0] * (n + 1)
        for (l, r) in queries:
            diff[l] += 1
            if r + 1 < n:
                diff[r + 1] -= 1

        # 2. 用 diff 计算前缀和，得到 cover[j]
        cover = [0] * n
        curr = 0
        for j in range(n):
            curr += diff[j]
            cover[j] = curr

        # 3. 检查每个位置 j：如果被查询覆盖的次数 < nums[j]，则不可能
        for j in range(n):
            if cover[j] < nums[j]:
                return False

        # 4. 全部通过，说明可以分配减操作，返回 True
        return True