LeetCode 3356. Zero Array Transformation II (2025/3/13每日一题)

标题：zero Array Transformation II

题目：

You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri, vali].

Each queries[i] represents the following action on nums:

• Decrement the value at each index in the range [li, ri] in nums by at most vali.
• The amount by which each value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

Example 1:

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

Output: 2

Explanation:

• For i = 0 (l = 0, r = 2, val = 1):
  • Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
  • The array will become [1, 0, 1].
• For i = 1 (l = 0, r = 2, val = 1):
  • Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
  • The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.

Example 2:

Input: nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]

Output: -1

Explanation:

• For i = 0 (l = 1, r = 3, val = 2):
  • Decrement values at indices [1, 2, 3] by [2, 2, 1] respectively.
  • The array will become [4, 1, 0, 0].
• For i = 1 (l = 0, r = 2, val = 1):
  • Decrement values at indices [0, 1, 2] by [1, 1, 0] respectively.
  • The array will become [3, 0, 0, 0], which is not a Zero Array.

题意理解：这道题理解起来稍微有点绕，给定一个一维数组nums, 和一个二维数组queries, queries[i] = [l_i, r_i, val_i] ,在nums数组中l_i到r_i中所有元素最大可以减掉val_i，问最少经过queries中的几步可以将nums变成全零数组。

暴力方法：每经过queries中的一个元素，即将nums中对应的元素减去val_i,，比较到第几步时全变为0。但看到数据量是10的5次方，这种暴力方法肯定不行。因此可以优化为二分查找，每次减到第mid处，判断一次是否为全零，如果是，则往前找，如果不是，再往后找。 判断是否为全零也可以优化，用一个单独的数组array记录元素变化，用类似线扫描的方法扫描queries，到第i个元素时array[queries[i][0]] += queries[i][2], array[queries[i][1] + 1] -= queries[i][2].

代码如下：

class Solution {
public:
    bool zeroArray(vector<int>& nums, vector<vector<int>>& queries, int idx) {
        int n = nums.size(), sum = 0;
        vector<int> array(n + 1);
        for (int i = 0; i < idx; i++){
            array[queries[i][0]] += queries[i][2];
            array[queries[i][1] + 1] -= queries[i][2];
        }
        for (int i = 0; i < n; i++){
            sum += array[i];
            if (sum < nums[i]) return false;
        }
        return true;
    }

    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = queries.size(), left = 0, right = queries.size();
        if(!zeroArray(nums, queries, right)) return -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canFormZeroArray(nums, queries, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

时间复杂度O（log(M) * (N+M)）,空间复杂度是O(N)

方法二：线扫描 + 线段树方法。（这个算法公主有空研究研究再写，线段树和线扫描都是公主的知识漏洞）