3362. 零数组变换 III（优先队列 + 差分数组）

题目描述

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

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

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

• 坐标范围内每一个元素减少的值相互 独立 。

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

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

题目链接

https://leetcode.cn/problems/zero-array-transformation-iii

示例输入

示例 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

解题思路

今天这题延续了这几天的“零数组变换”系列题目核心思路 —— 差分数组，不过相比之前，这题更具策略性：我们不再是判断是否能变成零数组，而是要 最多删除多少个查询操作，使得剩下的操作仍能让 nums 变成全 0。

这意味着：我们不能“随便选查询执行”，而是要选择 最有价值的查询 来用。

关键思路：

• 对于每个位置 i，我们希望让它在操作后变成 0，即 nums[i] 的值被累计减去。

• 每次操作只能将 [l, r] 范围内的元素 最多减1，这意味着每个元素最多被影响 nums[i] 次。

• 想让 nums[i] 变 0，我们要选择尽可能“覆盖 i 且右端尽量大”的操作 —— 因为右端越大，剩下的影响范围越广，保留价值也越大。

• 因此，我们可以按左端点升序排序操作，再用一个大顶堆来按右端点降序贪心挑选每个位置的最佳操作。

差分模拟 + 优先队列：

• 使用 pre[] 差分数组记录“前缀减少”的效果

• 每当发现当前 nums[i] + prefixSum > 0 时，就从堆中挑一个右端最大（也就是影响力最大）的操作

• 用它来减少当前位置值（即 prefixSum--），并在其右端点之后回补（pre[r+1]++）以恢复后续影响

• 最终堆中剩下的操作即为可以删除的操作数

代码实现

class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {
        Arrays.sort(queries, Comparator.comparingInt(e -> e[0]));
        PriorityQueue<Integer> queue = new PriorityQueue<>((e1, e2) -> e2 - e1);
        int n = nums.length;
        int[] pre = new int[n + 1];
        int prefixSum = 0;
        int q = 0;
        for (int i = 0; i < n; i++) {
            prefixSum += pre[i];
            while (q < queries.length && queries[q][0] <= i) {
                queue.add(queries[q][1]);
                q++;
            }
            while (nums[i] + prefixSum > 0 && !queue.isEmpty() && queue.peek() >= i) {
                prefixSum--;
                pre[queue.poll() + 1]++;
            }
            if (nums[i] + prefixSum > 0) {
                return -1;
            }
        }
        return queue.size();
    }
}

复杂度分析

• ⏱️ 时间复杂度：

  • O(n log m)，其中 n 是 nums 的长度，m 是 queries 的数量。排序和堆操作都基于 log m

• 🧠 空间复杂度：

  • O(n + m)，使用了差分数组和一个堆来辅助模拟操作

总结

这题是对差分数组技巧的再次延伸，并引入了贪心策略与堆优化的组合。比起前两天的题目，这次更考验我们如何在“影响范围”和“覆盖效率”之间做选择。整个过程的核心在于：用差分高效模拟区间操作、用堆贪心挑选最值钱的操作。

在理解差分本质之后，加入更多优化策略其实也就顺理成章了 🤗

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。