【Leetcode 每日一题】3362. 零数组变换 III

问题背景

给你一个长度为 $n$ 的整数数组 $nums$ 和一个二维数组 $queries$，其中 $queries[i]=[l_i,r_i]$。
每一个 $queries[i]$ 表示对于 $nums$ 的以下操作：

• 将 $nums$ 中下标在范围 $[l_i,r_i]$ 之间的每一个元素 最多 减少 $1$。
• 坐标范围内每一个元素减少的值相互 独立 。
  零数组 指的是一个数组里所有元素都等于 $0$。
  请你返回 最多 可以从 $queries$ 中删除多少个元素，使得 $queries$ 中剩下的元素仍然能将 $nums$ 变为一个 零数组 。如果无法将 $nums$ 变为一个 零数组 ，返回 $-1$。

数据约束

• $1\le nums.length\le 10^5$
• $0\le nums[i]\le 10^5$
• $1\le queries.length\le 10^5$
• $queries[i].length=2$
• $0\le l_i\le r_i<nums.length$

解题过程

本题与 零数组变换 II 的区别在于数组可以不按顺序使用，那么一个比较明显的贪心思路是，在每个位置上选择可能的范围最大的数组，这样后续某些位置上就可以不必操作，提高效率。
每个位置上的最大右端点，可以用最大堆来维护。

具体实现

class Solution {public int maxRemoval(int[] nums, int[][] queries) {Arrays.sort(queries, (o1, o2) -> o1[0] - o2[0]);PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);int n = nums.length;int[] diff = new int[n + 1];int num = 0;int j = 0;for (int i = 0; i < n; i++) {num += diff[i];while (j < queries.length && queries[j][0] <= i) {heap.add(queries[j][1]);j++;}while (num < nums[i] && !heap.isEmpty() && heap.peek() >= i) {num++;diff[heap.poll() + 1]--;}if (num < nums[i]) {return -1;}}return heap.size();}
}