Problem: 3362. 零数组转化 III

[TOC]

思路

应该先做一下这题，理解下里面的双指针解法：
3356. 零数组变换 II

排序

题目转化为从queries，选取部分项，使原数组转化成零数组。跟 3356. 零数组变换 II 这题的区别其实就是不考虑执行顺序了，因此先排个序：

        # l 升序
        queries.sort()

双指针 + 堆

可以先做下会议室系列：
2402. 会议室 III

• i指针指向nums数组
• j指针指向queries数组
• diff，若选上queries中某一项，则追加到差分数组上
• pre，i指针移动过程中维护前缀和

流程

对于queries中每一项，都有可能进入以下区域：

• 待选区，根据j指针移动来遍历每一个待选值
• 候选区，选取 queries[j] 后，以 r = queries[j][1] 值塞入最大堆 heap 候选区中
• 选中区，贪心，从heap 候选区中弹出最远的r值，写入diff，选中区中

        while i < n:
            num = nums[i]
            while j < m and queries[j][0] <= i:
                # r最大堆
                heappush(heap,-queries[j][1])
                j += 1
            # print(i,heap)
            # 当前差分前缀和不够，从heap中取，要保持
            while pre + diff[i] < num and heap:
                r = -heappop(heap)
                # 没用，扔掉
                if r < i:
                    res += 1
                # 有用，进入差分
                else:
                    diff[i] += 1
                    diff[r+1] -= 1
            # 满足不了题目
            if pre + diff[i] < num:
                return -1

            pre += diff[i]
            i += 1

总结

这种双指针 + 堆，我都归纳为会议安排类的题目，理解双指针以及堆在其中的作用才能更好地做这类题，一开始我也有点蒙，理解了就好了。。。。

更多题目模板总结，请参考2023年度总结与题目分享

Code

###Python3

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        # l 升序
        queries.sort()
        n,m = len(nums),len(queries)
        
        # nums 指针
        i = 0
        # queries 指针，代表待选区
        j = 0
        # 候选区，选取 queries 后，以 r 值塞入最大堆 
        heap = []
        # 选中区，选中后维护差分数组
        diff = [0] * (n + 1)
        # 维护前缀和
        pre = 0
        # 结果
        res = 0
        
        while i < n:
            num = nums[i]
            # 待选区 进入 候选区
            while j < m and queries[j][0] <= i:
                # r最大堆
                heappush(heap,-queries[j][1])
                j += 1

            # 候选区 进入 选中区
            # 当前差分前缀和不够，从heap中取，要保持
            while pre + diff[i] < num and heap:
                r = -heappop(heap)
                # 没用，扔掉
                if r < i:
                    res += 1
                # 有用，进入差分
                else:
                    diff[i] += 1
                    diff[r+1] -= 1
            # 满足不了题目
            if pre + diff[i] < num:
                return -1

            # 维护前缀和
            pre += diff[i]
            i += 1

        # 统计剩下的不需要的 queries
        res += len(heap)
        while j < m:
            res += 1
            j += 1
        return res