【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;
    }
}