M3356.零数组变换 II

binary search, prefix sum, https://leetcode.cn/problems/zero-array-transformation-ii/

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

每个 queries[i] 表示在 nums 上执行以下操作：

将 nums 中 [li, ri] 范围内的每个下标对应元素的值最多减少 vali。
每个下标的减少的数值可以独立选择。

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

返回 k 可以取到的 最小非负 值，使得在顺序处理前 k 个查询后，nums 变成 零数组。如果不存在这样的 k，则返回 -1。

示例 1：

输入： 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。

示例 2：

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

输出： -1

解释：

对于 i = 0（l = 1, r = 3, val = 2）：
- 在下标 [1, 2, 3] 处分别减少 [2, 2, 1]。
- 数组将变为 [4, 1, 0, 0]。
对于 i = 1（l = 0, r = 2, val = 1）：
- 在下标 [0, 1, 2] 处分别减少 [1, 1, 0]。
- 数组将变为 [3, 0, 0, 0]，这不是一个零数组。

提示：

1 <= nums.length <= 10^5
0 <= nums[i] <= 5 * 10^5
1 <= queries.length <= 10^5
queries[i].length == 3
0 <= li <= ri < nums.length
1 <= vali <= 5

这个题目是一个典型的 二分 + 差分数组 + 贪心验证 的问题。

🧠 核心思路：

我们要找到 最小的 k，使得前 k 个操作后数组可以变成全 0。注意操作里 "每个位置可以最多减少 val"，而且每个位置可以单独选择减多少。

所以我们不能强加一个固定的操作，而是判断某个 k 的前缀操作是否有可能使得数组变成全 0。显然，这种“是否可行”的判断是单调的：如果第 k 个操作能使数组变成全 0，那更大的 k 也可以。因此我们可以使用二分来查找这个最小的 k。

🔧 技术细节：

差分数组

我们可以将前 k 个操作作用起来形成一个「差分数组」，从而快速构造每个位置最多可以减少多少。

python

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)

        # 判断前k个queries是否可以让nums变为零数组
        def can_zero(k):
            diff = [0] * (n + 1)
            for i in range(k):
                l, r, val = queries[i]
                diff[l] += val
                diff[r + 1] -= val

            # 前缀和恢复每个位置可以最多减少的值
            max_decrease = [0] * n
            curr = 0
            for i in range(n):
                curr += diff[i]
                max_decrease[i] = curr

            # 每个位置最多能减 max_decrease[i]，但必须让 nums[i] == 0
            for i in range(n):
                if max_decrease[i] < nums[i]:
                    return False
            return True

        # 二分答案
        left, right = 0, len(queries)
        answer = -1

        while left <= right:
            mid = (left + right) // 2
            if can_zero(mid):
                answer = mid
                right = mid - 1  # 尝试更小的k
            else:
                left = mid + 1

        return answer

✅ 复杂度分析：

每次 can_zero(k) 是 O(n)
二分最多 log(q) 次
总复杂度：O(n log q)，可以通过 1e5 的数据

📌 示例解释：

python

nums = [2, 0, 2]
queries = [[0,2,1],[0,2,1],[1,1,3]]

k = 1 → 差分后 [1, 0, 1]，不能让 [2, 0, 2] 变成全0。
k = 2 → 差分后 [2, 0, 2]，正好可以让所有位置减到0 → ✅

M3356.零数组变换 II ​

M3356.零数组变换 II