3362. 零数组变换 III
题目描述
给你一个长度为 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 <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= li <= ri < nums.length
解法
方法一：贪心 + 差分数组 + 优先队列（大根堆）
Python3
class Solution:
def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
queries.sort()
pq = []
d = [0] * (len(nums) + 1)
s = j = 0
for i, x in enumerate(nums):
s += d[i]
while j < len(queries) and queries[j][0] <= i:
heappush(pq, -queries[j][1])
j += 1
while s < x and pq and -pq[0] >= i:
s += 1
d[-heappop(pq) + 1] -= 1
if s < x:
return -1
return len(pq)
Java
class Solution {
public int maxRemoval(int[] nums, int[][] queries) {
Arrays.sort(queries, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int n = nums.length;
int[] d = new int[n + 1];
int s = 0, j = 0;
for (int i = 0; i < n; i++) {
s += d[i];
while (j < queries.length && queries[j][0] <= i) {
pq.offer(queries[j][1]);
j++;
}
while (s < nums[i] && !pq.isEmpty() && pq.peek() >= i) {
s++;
d[pq.poll() + 1]--;
}
if (s < nums[i]) {
return -1;
}
}
return pq.size();
}
}
C++
class Solution {
public:
int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
sort(queries.begin(), queries.end());
priority_queue<int> pq;
int n = nums.size();
vector<int> d(n + 1, 0);
int s = 0, j = 0;
for (int i = 0; i < n; ++i) {
s += d[i];
while (j < queries.size() && queries[j][0] <= i) {
pq.push(queries[j][1]);
++j;
}
while (s < nums[i] && !pq.empty() && pq.top() >= i) {
++s;
int end = pq.top();
pq.pop();
--d[end + 1];
}
if (s < nums[i]) {
return -1;
}
}
return pq.size();
}
};
Go
func maxRemoval(nums []int, queries [][]int) int {
sort.Slice(queries, func(i, j int) bool {
return queries[i][0] < queries[j][0]
})
var h hp
heap.Init(&h)
n := len(nums)
d := make([]int, n+1)
s, j := 0, 0
for i := 0; i < n; i++ {
s += d[i]
for j < len(queries) && queries[j][0] <= i {
heap.Push(&h, queries[j][1])
j++
}
for s < nums[i] && h.Len() > 0 && h.IntSlice[0] >= i {
s++
end := heap.Pop(&h).(int)
if end+1 < len(d) {
d[end+1]--
}
}
if s < nums[i] {
return -1
}
}
return h.Len()
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
TypeScript
function maxRemoval(nums: number[], queries: number[][]): number {
queries.sort((a, b) => a[0] - b[0]);
const pq = new MaxPriorityQueue<number>();
const n = nums.length;
const d: number[] = Array(n + 1).fill(0);
let [s, j] = [0, 0];
for (let i = 0; i < n; i++) {
s += d[i];
while (j < queries.length && queries[j][0] <= i) {
pq.enqueue(queries[j][1]);
j++;
}
while (s < nums[i] && !pq.isEmpty() && pq.front() >= i) {
s++;
d[pq.dequeue() + 1]--;
}
if (s < nums[i]) {
return -1;
}
}
return pq.size();
}