M3355.零数组变换I

prefix sum, 区间重叠, https://leetcode.cn/problems/zero-array-transformation-i/

给定一个长度为 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^5
0 <= nums[i] <= 10^5
1 <= queries.length <= 10^5
queries[i].length == 2
0 <= li <= ri < nums.length

问题理解

我们有一个整数数组 nums 和一个二维数组 queries，其中每个 queries[i] = [li, ri] 表示一次查询的范围。

在每次查询中：

我们可以在这个区间 [li, ri] 中选择任意一组下标。
然后将这些位置上的元素都减 1。
每次查询只能进行一次这样的操作（选一组子集并减 1）。

最终目标是：是否可以通过一系列这样的操作，让最后整个数组变成全零？

这其实是一个差分数组或者前缀和类型的问题。

解题思路

我们可以把每个查询的操作看作是对某个区间加了一个“减 1 的操作”，然后我们要判断这些操作是否能覆盖 nums 中的每个数所需要的减量。

更具体地说：

假设我们用一个数组 diff 来记录每个位置上被多少个查询影响了。

我们遍历所有 queries，对每个 [li, ri]，使用差分技巧：

text

diff[li] += 1
diff[ri + 1] -= 1

然后计算前缀和，就能知道每个位置 i 被执行了多少次减 1 的机会。

如果这个值 >= nums[i]，那就可以做到；否则不行。

实现步骤

初始化一个长度为 n 的差分数组 diff。
遍历每个查询 [l, r]，更新 diff[l] += 1，diff[r + 1] -= 1。
对 diff 数组求前缀和，得到每个位置上的操作次数。
检查每个位置的操作次数是否 ≥ nums[i]。

如果是全部满足，则返回 true；否则返回 false。

python

def canConvert(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

    # 前缀和得到每个位置的操作次数
    ops = [0] * n
    ops[0] = diff[0]
    for i in range(1, n):
        ops[i] = ops[i - 1] + diff[i]

    for i in range(n):
        if ops[i] < nums[i]:
            return False
    return True

M3355.零数组变换I ​

M3355.零数组变换I