今日题目

https://leetcode.com/problems/zero-array-transformation-iii/

思路

本题要求我们找到"有用"的区间数量，换句话说，即使数组变为零数组所需的最少区间数。

解题的关键在于转换视角：如果我们单独看待数组中的每个元素，就可以用贪心算法来解决这个问题。

道理很简单——要使整个数组变为零数组，必须让每个元素都变为零。

对于每个元素，最优的策略是选择覆盖该元素且右端点尽可能靠右的区间。因为右端点越远，未来能覆盖的元素就越多，相比右端点较短的区间总是更优的选择。

因此，我们需要一个数据结构来动态维护当前"最远右端点"。这个数据结构需要支持动态插入和删除最大值，堆（优先队列）正是存储"右端点"的最佳选择。

算法

基于上述分析，我们可以构建以下算法：

1. 首先，以查询的左端点为关键字对查询数组排序，这样就能快速找到左端点不大于当前下标的所有查询。
2. 创建一个差分数组来处理区间叠加操作；一个大根堆来存储查询的右端点；一个索引记录遍历查询时的当前位置。
3. 遍历数字数组：对于每个元素，先将所有左端点不大于当前下标的查询入堆，堆中的所有元素均有可能用于减少当前元素的值。
4. 然后处理当前元素，从堆中贪心地选取可用查询并执行区间减操作。（通过验证堆顶右端点大于等于当前下标来保证操作的合法性——此时左端点必然不大于当前下标，右端点也必然不小于当前下标，从而确保每次操作均有效。）
5. 最后，若当前元素仍大于 0，则返回 -1；否则返回堆 h 中剩余元素的数量，即所有未被使用的查询数。

复杂度

• 时间复杂度：

$O(N \times log(m))$

• 空间复杂度：

$O(N + M)$

代码

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        queries.sort(key = lambda x: x[0])
        diff = [0] * (len(nums) + 1)
        h = []
        idx, now = 0,0

        for i in range(len(nums)):
            while idx < len(queries) and queries[idx][0] <= i:
                heappush(h, -queries[idx][1])
                idx += 1
            
            now += diff[i]

            while h and now < nums[i] and -h[0] >= i:
                now += 1
                diff[-heappop(h) + 1] -= 1

            if now < nums[i]:
                return -1
            
        return len(h)

更多题解请访问 我的博客