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 = [li, ri, vali].
Each queries 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 = [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[0]] += queries[2], array[queries[1] + 1] -= queries[2].
代码如下：

1. class Solution {
2. public:
3.     bool zeroArray(vector<int>& nums, vector<vector<int>>& queries, int idx) {
4.         int n = nums.size(), sum = 0;
5.         vector<int> array(n + 1);
6.         for (int i = 0; i < idx; i++){
7.             array[queries[i][0]] += queries[i][2];
8.             array[queries[i][1] + 1] -= queries[i][2];
9.         }
10.         for (int i = 0; i < n; i++){
11.             sum += array[i];
12.             if (sum < nums[i]) return false;
13.         }
14.         return true;
15.     }
17.     int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
18.         int n = queries.size(), left = 0, right = queries.size();
19.         if(!zeroArray(nums, queries, right)) return -1;
21.         while (left <= right) {
22.             int mid = left + (right - left) / 2;
23.             if (canFormZeroArray(nums, queries, mid)) {
24.                 right = mid - 1;
25.             } else {
26.                 left = mid + 1;
27.             }
28.         }
29.         return left;
30.     }
31. };

复制代码

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

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。