shelterofly

目标

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

每一个 queries[i] 表示对于 nums 的以下操作：

• 将 nums 中下标在范围 [li, ri] 之间的每一个元素 最多 减少 1 。
• 坐标范围内每一个元素减少的值相互 独立 。

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

请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组 。如果无法将 nums 变为一个 零数组 ，返回 -1 。

示例 1：

输入：nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
输出：1
解释：
删除 queries[2] 后，nums 仍然可以变为零数组。
对于 queries[0] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。
对于 queries[1] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。

示例 2：

输入：nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
输出：2
解释：
可以删除 queries[2] 和 queries[3] 。

示例 3：

输入：nums = [1,2,3,4], queries = [[0,3]]
输出：-1
解释：
nums 无法通过 queries 变成零数组。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= li <= ri < nums.length

思路

有一个长度为 n 的整数数组，每一次操作可以将给定范围内的任意元素减 1，返回最多可以删掉多少个操作，使得剩下的操作能够将数组中的所有元素变为 0。

对于元素 nums[0] 要将其变为 0 必须要操作 nums[0] 次，且操作范围必须包括 0，因此可以按照操作范围的左端点排序，每次选择右端点最远即覆盖最广的操作区间。可以维护一个由大到小的优先队列，从操作中选出左端点小于等于当前下标的操作，将其右端点放入队列。从队列中取出右端点大于等于当前下标的操作，使用差分数组进行区间修改。

代码

/**
 * @date 2025-05-22 23:02
 */
public class MaxRemoval3362 {

    public int maxRemoval(int[] nums, int[][] queries) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        Arrays.sort(queries, (a, b) -> a[0] - b[0]);
        int n = nums.length;
        int[] diff = new int[n + 1];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        int num = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            num += diff[i];
            while (k < queries.length && queries[k][0] <= i) {
                q.offer(queries[k++][1]);
            }
            while (!q.isEmpty() && q.peek() >= i && num > 0) {
                diff[q.poll() + 1]++;
                num--;
            }
            if (num > 0) {
                return -1;
            }
        }
        return q.size();
    }

}

性能

目标

给你一个长度为 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

思路

有一个长度为 n 的整数数组，每一次操作可以将给定范围内的任意元素 最多 减去 vali = queries[2]，计算将数组中的所有元素变为 0 最少需要按顺序操作几次。

与 3355.零数组变换I 相比，求的是最小操作次数，每一次操作都需要判断数组元素是否全为 0，涉及到区间修改与区间查询，可以使用线段树维护区间最大值，每次操作后判断最大值是否大于 0。

官网给出了另一种思路，二分查找操作次数 k，针对每一个 k 问题变成 3355.零数组变换I。

代码

/**
 * @date 2025-05-21 9:35
 */
public class MinZeroArray3356 {

    public int minZeroArray(int[] nums, int[][] queries) {
        int right = queries.length - 1;
        int left = -1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            if (check(nums, mid, queries)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = left + (right - left) / 2;
        }
        return left == queries.length ? -1 : left + 1;
    }

    public boolean check(int[] nums, int k, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        for (int i = 0; i <= k; i++) {
            int[] query = queries[i];
            int val = query[2];
            diff[query[0]] -= val;
            diff[query[1] + 1] += val;
        }
        int num = 0;
        for (int i = 0; i < n; i++) {
            num += diff[i];
            if (num > 0) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

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

对于每个查询 queries[i]：

• 在 nums 的下标范围 [li, ri] 内选择一个下标 子集。
• 将选中的每个下标对应的元素值减 1。

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

如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。

示例 1：

输入： nums = [1,0,1], queries = [[0,2]]
输出： true
解释：
对于 i = 0：
选择下标子集 [0, 2] 并将这些下标处的值减 1。
数组将变为 [0, 0, 0]，这是一个零数组。

示例 2：

输入： nums = [4,3,2,1], queries = [[1,3],[0,2]]
输出： false
解释：
对于 i = 0： 
选择下标子集 [1, 2, 3] 并将这些下标处的值减 1。
数组将变为 [4, 2, 1, 0]。
对于 i = 1：
选择下标子集 [0, 1, 2] 并将这些下标处的值减 1。
数组将变为 [3, 1, 0, 0]，这不是一个零数组。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= li <= ri < nums.length

思路

有一个长度为 n 的整数数组，每一次操作可以将给定范围内的任意元素减 1，判断操作完成后能否将数组中的所有元素变为 0。

使用差分数组批量修改元素，最后判断是否存在元素大于 0 即可。

代码

/**
 * @date 2025-05-20 9:37
 */
public class IsZeroArray3355 {

    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        for (int[] query : queries) {
            diff[query[0]] -= 1;
            diff[query[1] + 1] += 1;
        }
        int num = 0;
        for (int i = 0; i < n; i++) {
            num += diff[i];
            if (num > 0) {
                return false;
            }
        }
        return true;
    }

}

性能