2025-06-08：零数组变换Ⅱ。用go语言，给定一个长度为 n 的整数数组 nums 和一个包含多个查询的二维数组 quer

2025-06-08：零数组变换Ⅱ。用go语言，给定一个长度为 n 的整数数组 nums 和一个包含多个查询的二维数组 queries，其中每个查询 queries[i] = [li, ri, vali]，表示对数组 nums 中索引区间 [li, ri] 内的元素执行如下操作：

对于区间内的每个元素，可以最多减少 vali（每个元素减少的量可独立选择，但不能超过 vali）。

定义“零数组”为所有元素均为 0 的数组。

要求找到一个最小的非负整数 k，满足按顺序执行前 k 条查询后，数组 nums 变成零数组。如果不存在这样的 k，返回 -1。

1 <= nums.length <= 100000。

0 <= nums[i] <= 5 * 100000。

1 <= queries.length <= 100000。

queries[i].length == 3。

0 <= li <= ri < nums.length。

1 <= vali <= 5。

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

输出： 2。

解释：

对于 i = 0（l = 0, r = 2, val = 1）：

在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。

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

对于 i = 1（l = 0, r = 2, val = 1）：

在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。

数组将变为 [0, 0, 0]，这是一个零数组。因此，k 的最小值为 2。

题目来自力扣3356。

解决思路

1. 1. 贪心策略：为了最小化 k，我们需要尽可能早地满足每个 nums[i] 的归零需求。即，对于每个 nums[i]，我们需要计算覆盖它的查询的 vali 之和是否至少为 nums[i]。
2. 2. 差分数组：为了高效计算每个位置 i 被多少查询覆盖以及这些查询的 vali 之和，可以使用差分数组技术。差分数组可以高效地处理区间更新（即对 [li, ri] 区间内的所有元素加 vali）。
3. 3. 按顺序处理查询：我们需要按顺序处理查询，并在处理过程中动态维护每个位置的剩余需要减少的值。如果某个位置的剩余值在查询处理完后仍然大于 0，则无法归零，返回 -1。

详细步骤

1. 1. 初始化：
   • • 创建一个差分数组 deltaArray，长度为 n+1（n 是 nums 的长度），初始化为 0。
   • • 初始化 operations 为 0，表示当前已累积的减少量。
   • • 初始化 k 为 0，表示当前已处理的查询数量。
2. 2. 遍历数组 nums：
   • • 对于每个 nums[i]（i 从 0 到 n-1）：
     • • 将 deltaArray[i] 的值加到 operations 中（operations 表示当前 nums[i] 已累积的减少量）。
     • • 如果 operations < nums[i]，则需要处理更多的查询：
       • • 按顺序处理后续查询（从 k 开始），直到 operations >= nums[i] 或没有更多查询：
         • • 对于每个查询 [left, right, value]：
         • • 更新差分数组：deltaArray[left] += value，deltaArray[right+1] -= value。
         • • 如果当前 i 在 [left, right] 区间内，则 operations += value（因为当前查询可以直接减少 nums[i]）。
         • • 增加 k（表示已处理该查询）。
       • • 如果处理完所有查询后 operations 仍然小于 nums[i]，则返回 -1。
     • • 如果 operations >= nums[i]，则继续处理下一个 nums[i]。
3. 3. 返回结果：
   • • 如果所有 nums[i] 都满足 operations >= nums[i]，则返回 k（即需要的最少查询数量）。
   • • 否则返回 -1。

时间复杂度和空间复杂度

• • 时间复杂度：
  • • 遍历 nums 数组：O(n)。
  • • 处理查询：每个查询最多被处理一次，O(m)（m 是查询数量）。
  • • 总时间复杂度：O(n + m)。
• • 空间复杂度：
  • • 差分数组：O(n)。
  • • 其他变量：O(1)。
  • • 总空间复杂度：O(n)。

总结

通过贪心策略和差分数组技术，我们可以在线性时间内高效地解决问题。算法的时间复杂度为 O(n + m)，空间复杂度为 O(n)。

Go完整代码如下：

package main

import (
    "fmt"
)

func minZeroArray(nums []int, queries [][]int)int {
    n := len(nums)
    deltaArray := make([]int, n+1)
    operations := 0
    k := 0
    for i, num := range nums {
        operations += deltaArray[i]
        for k < len(queries) && operations < num {
            left, right, value := queries[k][0], queries[k][1], queries[k][2]
            deltaArray[left] += value
            deltaArray[right+1] -= value
            if left <= i && i <= right {
                operations += value
            }
            k++
        }
        if operations < num {
            return-1
        }
    }
    return k
}

func main() {
    nums := []int{2, 0, 2}
    queries := [][]int{{0, 2, 1}, {0, 2, 1}, {1, 1, 3}}
    fmt.Println(minZeroArray(nums, queries))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def minZeroArray(nums, queries):
    n = len(nums)
    deltaArray = [0] * (n + 1)
    operations = 0
    k = 0
    for i, num inenumerate(nums):
        operations += deltaArray[i]
        while k < len(queries) and operations < num:
            left, right, value = queries[k]
            deltaArray[left] += value
            if right + 1 < len(deltaArray):
                deltaArray[right + 1] -= value
            if left <= i <= right:
                operations += value
            k += 1
        if operations < num:
            return -1
    return k


if __name__ == "__main__":
    nums = [2, 0, 2]
    queries = [[0, 2, 1], [0, 2, 1], [1, 1, 3]]
    print(minZeroArray(nums, queries))