贪心+最大堆+差分数组（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2024年11月24日 07:17

前置题目：3355. 零数组变换 I

以 $\textit{nums}=[2,0,2,0,2]$ 为例。

从左到右遍历数组。对于 $\textit{nums}[0]=2$ 来说，我们必须从 $\textit{queries}$ 中选两个左端点为 $0$ 的区间。选哪两个呢？

贪心地想，区间的右端点越大越好，后面的元素越小，后续操作就越少。所以选两个左端点为 $0$，且右端点最大的区间。

继续遍历，由于 $\textit{nums}[1]=0$，可以直接跳过。

继续遍历，如果 $\textit{nums}[2]$ 仍然大于 $0$，我们需要从左端点 $\le 2$ 的未选区间中，选择右端点最大的区间。

这启发我们用最大堆维护左端点 $\le i$ 的未选区间的右端点。

剩下的就是用差分数组去维护区间减一了。你需要先完成 3355. 零数组变换 I 这题。

最终堆的大小（剩余没有使用的区间个数）就是答案。

代码实现时，还需要把 $\textit{queries}$ 按照左端点排序，这样我们可以用双指针遍历 $\textit{nums}$ 和左端点 $\le i$ 的区间。

具体请看视频讲解，欢迎点赞关注~

###py

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        queries.sort(key=lambda q: q[0])  # 按照左端点从小到大排序
        h = []
        diff = [0] * (len(nums) + 1)
        sum_d = j = 0
        for i, x in enumerate(nums):
            sum_d += diff[i]
            # 维护左端点 <= i 的区间
            while j < len(queries) and queries[j][0] <= i:
                heappush(h, -queries[j][1])  # 取相反数表示最大堆
                j += 1
            # 选择右端点最大的区间
            while sum_d < x and h and -h[0] >= i:
                sum_d += 1
                diff[-heappop(h) + 1] -= 1
            if sum_d < x:
                return -1
        return len(h)

###java

class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {
        Arrays.sort(queries, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int n = nums.length;
        int[] diff = new int[n + 1];
        int sumD = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {
            sumD += diff[i];
            // 维护左端点 <= i 的区间
            while (j < queries.length && queries[j][0] <= i) {
                pq.add(queries[j][1]);
                j++;
            }
            // 选择右端点最大的区间
            while (sumD < nums[i] && !pq.isEmpty() && pq.peek() >= i) {
                sumD++;
                diff[pq.poll() + 1]--;
            }
            if (sumD < nums[i]) {
                return -1;
            }
        }
        return pq.size();
    }
}

###cpp

class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        ranges::sort(queries, {}, [](auto& q) { return q[0]; }); // 按照左端点从小到大排序
        int n = nums.size(), j = 0, sum_d = 0;
        vector<int> diff(n + 1, 0);
        priority_queue<int> pq;
        for (int i = 0; i < n; i++) {
            sum_d += diff[i];
            // 维护左端点 <= i 的区间
            while (j < queries.size() && queries[j][0] <= i) {
                pq.push(queries[j][1]);
                j++;
            }
            // 选择右端点最大的区间
            while (sum_d < nums[i] && !pq.empty() && pq.top() >= i) {
                sum_d++;
                diff[pq.top() + 1]--;
                pq.pop();
            }
            if (sum_d < nums[i]) {
                return -1;
            }
        }
        return pq.size();
    }
};

###go

func maxRemoval(nums []int, queries [][]int) int {
slices.SortFunc(queries, func(a, b []int) int { return a[0] - b[0] })
h := hp{}
diff := make([]int, len(nums)+1)
sumD, j := 0, 0
for i, x := range nums {
sumD += diff[i]
// 维护左端点 <= i 的区间
for ; j < len(queries) && queries[j][0] <= i; j++ {
heap.Push(&h, queries[j][1])
}
// 选择右端点最大的区间
for sumD < x && h.Len() > 0 && h.IntSlice[0] >= i {
sumD++
diff[heap.Pop(&h).(int)+1]--
}
if sumD < x {
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 }

复杂度分析

时间复杂度：$\mathcal{O}(n + q\log q)$，其中 $n$ 是 $\textit{nums}$ 的长度，$q$ 是 $\textit{queries}$ 的长度。
空间复杂度：$\mathcal{O}(n+q)$。

相似题目

871. 最低加油次数

另外，可以做做下面贪心题单中的「§1.9 反悔贪心」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

普通视图

复杂度分析

相似题目

分类题单