Medium
题目描述
给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。
每个 queries[i] 表示对 nums 执行以下操作：
- 将
nums中范围[li, ri]内每个索引的值最多减 1。 - 每个索引减少的量可以独立选择。
零数组是所有元素都等于 0 的数组。
返回可以从 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 也无法转换为零数组。
约束条件：
1 <= nums.length <= 10^50 <= nums[i] <= 10^51 <= queries.length <= 10^5queries[i].length == 20 <= li <= ri < nums.length
解题思路
这道题要求我们找出可以移除的查询的最大数量，使得剩余查询仍能将数组转换为零数组。
核心思路：
贪心策略：我们希望尽可能多地移除查询，因此需要贪心地选择必要的查询。关键insight是：对于每个位置，我们应该优先使用右端点更远的查询，因为这些查询更有可能覆盖后续位置。
扫描线算法：
- 按查询的左端点排序，使用扫描线从左到右处理每个位置
- 对于每个位置，维护所有可以覆盖该位置的查询（左端点 ≤ 当前位置）
- 使用优先队列（最大堆）存储这些查询的右端点，优先选择右端点最远的查询
具体步骤：
- 将查询按左端点排序
- 从左到右扫描每个位置
- 对于位置i，将所有左端点为i的查询加入候选集合
- 移除所有右端点小于i的查询（已经无法覆盖当前位置）
- 贪心地选择nums[i]个右端点最大的查询来覆盖位置i
- 如果可用查询数量不足，返回-1
这种方法确保我们使用最少的查询来满足需求，从而最大化可移除的查询数量。
代码实现
class Solution {
public:
int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size(), m = queries.size();
// 给查询添加索引并按左端点排序
vector<pair<int, int>> sortedQueries;
for (int i = 0; i < m; i++) {
sortedQueries.push_back({queries[i][0], queries[i][1]});
}
sort(sortedQueries.begin(), sortedQueries.end());
priority_queue<int> available; // 存储可用查询的右端点（最大堆）
int queryIndex = 0;
int used = 0; // 已使用的查询数量
for (int i = 0; i < n; i++) {
// 添加所有左端点为i的查询
while (queryIndex < m && sortedQueries[queryIndex].first == i) {
available.push(sortedQueries[queryIndex].second);
queryIndex++;
}
// 移除右端点小于i的查询
while (!available.empty() && available.top() < i) {
available.pop();
}
// 贪心选择nums[i]个右端点最大的查询
int need = nums[i];
while (need > 0 && !available.empty()) {
available.pop();
used++;
need--;
}
// 如果无法满足需求，返回-1
if (need > 0) {
return -1;
}
}
return m - used;
}
};
class Solution:
def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
import heapq
n, m = len(nums), len(queries)
# 按左端点排序查询
queries.sort()
available = [] # 最大堆存储可用查询的右端点
query_index = 0
used = 0 # 已使用的查询数量
for i in range(n):
# 添加所有左端点为i的查询
while query_index < m and queries[query_index][0] == i:
# Python的heapq是最小堆，所以存储负值来模拟最大堆
heapq.heappush(available, -queries[query_index][1])
query_index += 1
# 移除右端点小于i的查询
while available and -available[0] < i:
heapq.heappop(available)
# 贪心选择nums[i]个右端点最大的查询
need = nums[i]
while need > 0 and available:
heapq.heappop(available)
used += 1
need -= 1
# 如果无法满足需求，返回-1
if need > 0:
return -1
return m - used
public class Solution {
public int MaxRemoval(int[] nums, int[][] queries) {
int n = nums.Length, m = queries.Length;
// 按左端点排序查询
Array.Sort(queries, (a, b) => a[0].CompareTo(b[0]));
var available = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a))); // 最大堆
int queryIndex = 0;
int used = 0; // 已使用的查询数量
for (int i = 0; i < n; i++) {
// 添加所有左端点为i的查询
while (queryIndex < m && queries[queryIndex][0] == i) {
available.Enqueue(queries[queryIndex][1], queries[queryIndex][1]);
queryIndex++;
}
// 移除右端点小于i的查询
while (available.Count > 0 && available.Peek() < i) {
available.Dequeue();
}
// 贪心选择nums[i]个右端点最大的查询
int need = nums[i];
while (need > 0 && available.Count > 0) {
available.Dequeue();
used++;
need--;
}
// 如果无法满足需求，返回-1
if (need > 0) {
return -1;
}
}
return m - used;
}
}
var maxRemoval = function(nums, queries) {
const n = nums.length;
const m = queries.length;
// Sort queries by left endpoint
queries.sort((a, b) => a[0] - b[0]);
// Check if it's possible to make all zeros with all queries
const diff = new Array(n + 1).fill(0);
for (const [l, r] of queries) {
diff[l]++;
diff[r + 1]--;
}
let current = 0;
for (let i = 0; i < n; i++) {
current += diff[i];
if (current < nums[i]) return -1;
}
// Binary search on the answer
let left = 0, right = m;
const canRemove = (k) => {
// Try to remove k queries greedily
const available = new Array(m).fill(true);
const removed = [];
// Priority queue simulation - use array and sort
const pq = [];
let queryIdx = 0;
const tempDiff = new Array(n + 1).fill(0);
let currentCover = 0;
for (let i = 0; i < n; i++) {
currentCover += tempDiff[i];
// Add all queries that start at position i
while (queryIdx < m && queries[queryIdx][0] === i) {
pq.push({end: queries[queryIdx][1], idx: queryIdx});
queryIdx++;
}
// Sort by end position (descending) to get max heap behavior
pq.sort((a, b) => b.end - a.end);
// Remove queries that end before current position
while (pq.length > 0 && pq[pq.length - 1].end < i) {
const query = pq.pop();
if (available[query.idx]) {
removed.push(query.idx);
available[query.idx] = false;
}
}
// Use queries greedily to cover nums[i]
let needed = nums[i] - currentCover;
while (needed > 0 && pq.length > 0) {
pq.sort((a, b) => b.end - a.end);
const query = pq.shift();
if (available[query.idx]) {
tempDiff[i]++;
tempDiff[query.end + 1]--;
currentCover++;
needed--;
available[query.idx] = true; // Mark as used, not removed
}
}
if (needed > 0) return false;
}
// Add remaining unused queries to removed list
for (let i = 0; i < m; i++) {
if (available[i]) {
let used = false;
for (let j = 0; j < m; j++) {
if (available[j] === true && j !== i) continue;
}
// Check if this query was actually used
let wasUsed = false;
for (const query of pq) {
if (query.idx === i && available[i] === true) {
wasUsed = true;
break;
}
}
if (!wasUsed) removed.push(i);
}
}
return removed.length >= k;
};
// Simpler greedy approach
const solve = () => {
const used = new Array(m).fill(false);
const events = [];
// Create events for query start/end
for (let i = 0; i < m; i++) {
events.push({pos: queries[i][0], type: 'start', idx: i});
events.push({pos: queries[i][1] + 1, type: 'end', idx: i});
}
events.sort((a, b) => a.pos - b.pos);
const available = [];
let eventIdx = 0;
let currentSum = 0;
for (let i = 0; i < n; i++) {
// Process events at position i
while (eventIdx < events.length && events[eventIdx].pos === i) {
const event = events[eventIdx];
if (event.type === 'start') {
available.push(event.idx);
} else {
const idx = available.indexOf(event.idx);
if (idx !== -1 && !used[event.idx]) {
available.splice(idx, 1);
}
}
eventIdx++;
}
// Use queries greedily
let needed = nums[i] - currentSum;
const toUse = [];
for (const queryIdx of available) {
if (!used[queryIdx] && needed > 0) {
toUse.push(queryIdx);
needed--;
}
}
for (const queryIdx of toUse) {
used[queryIdx] = true;
currentSum++;
// Schedule decrement
events.push({pos: queries[queryIdx][1] + 1, type: 'decrement', idx: queryIdx});
}
// Process decrements
while (eventIdx < events.length && events[eventIdx].pos === i + 1 && events[eventIdx].type === 'decrement') {
currentSum--;
eventIdx++;
}
if (needed > 0) return -1;
}
return used.filter(x => !x).length;
};
return solve();
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(m log m + n log m)，其中排序需要 O(m log m)，扫描过程中每个查询最多进出堆一次，总共 O(m log m) |
| 空间复杂度 | O(m)，主要是优先队列存储查询的空间开销 |
相关题目
. Corporate Flight Bookings (Medium)
. Zero Array Transformation IV (Medium)