零数组变换

题目描述

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

对于每个查询 queries[i]：

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

若在按顺序处理所有查询后，能够将 nums 转换为零数组（所有元素为 0），则返回 true，否则返回 false。

---

示例 1：

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

解释：
选择下标 [0, 2] 进行减 1，结果为 [0, 0, 0]，是零数组。

示例 2：

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

解释：
第一个查询：对 [1,2,3] 执行减1，变为 [4,2,1,0]；
第二个查询：对 [0,1,2] 执行减1，变为 [3,1,0,0]；
最终不是零数组。

---

初始解法（暴力，超时）

class Solution(object):
    def isZeroArray(self, nums, queries):
        n = len(nums)
        count = [0] * n  # 每个位置最多能被减的次数

        # 统计每个下标被操作的总次数
        for l, r in queries:
            for i in range(l, r + 1):
                count[i] += 1

        # 检查每个位置是否能被减到 0
        for i in range(n):
            if nums[i] > count[i]:
                return False
        return True

该方法效率低，时间复杂度为 O(n * q)，容易超时。

---

差分数组优化解法 ✅

class Solution(object):
    def isZeroArray(self, nums, queries):
        n = len(nums)
        diff = [0] * (n + 1)  # 差分数组初始化

        # 区间修改打点
        for l, r in queries:
            diff[l] += 1
            if r + 1 < n:
                diff[r + 1] -= 1

        # 构造前缀和，计算每个位置可被操作的次数
        curr = 0
        for i in range(n):
            curr += diff[i]
            if nums[i] > curr:
                return False
        return True

---

解法总结

• 建模本质：每个 [l, r] 查询意味着我们可以对该区间中任意下标减 1。问的是：“是否每个位置都可以被减够次数？”。
• 差分数组应用场景：当你需要频繁对某个区间 [l, r] 执行 +1 或 -1 操作时，差分数组可以将区间修改转为两个点的标记，计算前缀和即可还原每个位置的累计值。
• 本题中每个 nums[i] 都必须 ≤ 可操作次数 curr[i]，否则无法变为 0。
• 总时间复杂度 O(n + q)，适合大数据范围。

---