【Leetcode 每日一题】3356. 零数组变换 II

问题背景

给你一个长度为 $n$ 的整数数组 $nums$ 和一个二维数组 $queries$，其中 $queries[i]=[l_i,r_i,va{l}_i]$。
每个 $queries[i]$ 表示在 $nums$ 上执行以下操作：

• 将$nums$ 中 $[l_i,r_i]$ 范围内的每个下标对应元素的值 最多 减少 $va{l}_i$。
• 每个下标的减少的数值可以 独立 选择。

零数组 是指所有元素都等于 $0$ 的数组。
返回 $k$ 可以取到的 最小非负 值，使得在 顺序 处理前 $k$ 个查询后，$nums$ 变成 零数组。如果不存在这样的 $k$，则返回 $-1$。

数据约束

• $1\le nums.length\le 10^5$
• $0\le nums[i]\le 5\times 10^5$
• $1\le queries.length\le 10^5$
• $queries[i].length=3$
• $0\le l_i\le r_i<nums.length$
• $1\le va{l}_i\le 5$

解题过程

由于应用的查询越多，越有可能满足条件，所以答案是具有单调性的，可以考虑借助 零数组变换 I 结合二分查找来实现。
也可以在每个位置线性地执行所有可能的查询，根据各个位置是否符合要求来判断，这样用双指针完成，效率更高。

具体实现

二分查找

class Solution {public int minZeroArray(int[] nums, int[][] queries) {int n = queries.length;int left = 0, right = n + 1;while (left < right) {int mid = left + ((right - left) >>> 1);if (check(mid, nums, queries)) {right = mid;} else {left = mid + 1;}}return right <= n ? right : -1;}private boolean check(int k, int[] nums, int[][] queries) {int n = nums.length;int[] diff = new int[n + 1];for (int i = 0; i < k; i++) {int[] query = queries[i];int left = query[0], right = query[1], value = query[2];diff[left] += value;diff[right + 1] -= value;}int num = 0;for (int i = 0; i < n; i++) {num += diff[i];if (nums[i] > num) {return false;}}return true;}
}

双指针

class Solution {public int minZeroArray(int[] nums, int[][] queries) {int n = nums.length;int[] diff =  new int[n + 1];int num = 0;int k = 0;for (int i = 0; i < n; i++) {int cur = nums[i];num += diff[i];while (k < queries.length && num < cur) {int[] query = queries[k];int left = query[0], right = query[1], value = query[2];diff[left] += value;diff[right + 1] -= value;if (left <= i && i <= right) {num += value;}k++;}if (num < cur) {return -1;}}return k;}
}