目标
给你一个长度为 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();
}
}
性能
