【Leetcode Daily】480滑动窗口中位数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个数组和一个窗口大小 k，现在规定这个窗口从数组最左侧移到最右侧，求每个窗口的中位数。

思路分享

• 比起 【Leetcode Daily】295数据流的中位数，本题多加了需要删除的功能，但是对于堆而言，想要找到其中的值再删除，相当于重建，复杂度比较高。

• 这里就可以引入“懒删除堆”，顾名思义，这个堆删除值不会立刻删除，而是先记录下来，在做入堆，取堆顶等操作的同时，检查堆顶是否为需要删除的值，是则直接弹出堆顶，不是则照常操作。

  https://leetcode.cn/problems/sliding-window-median/solutions/3628827/295-ti-lan-shan-chu-dui-pythonjavacgojsr-66ch/

• 注意，对于大小堆这种写法引入删除后，注意保持 left 的 size 与 right 相等或者多 1，否则左右两边弹堆入堆调整一下。

代码解答（强烈建议自行解答后再看）

• 参考题解

class LazyHeap:
    def __init__(self):
        self.heap = []
        self.size = 0
        self.remove_cnt = defaultdict(int)
    
    def push(self, num):
        self.apply_remove()
        heappush(self.heap, num)
        self.size += 1

    def pop(self) -> int:
        self.size -= 1
        return heappop(self.heap)

    def pushpop(self, num) -> int:
        self.apply_remove()
        return heappushpop(self.heap, num)
    
    def top(self) -> int:
        self.apply_remove()
        return self.heap[0]
    
    def remove(self, num):
        self.remove_cnt[num] += 1
        self.size -= 1

    def apply_remove(self):
        while self.heap and self.remove_cnt[self.heap[0]]:
            self.remove_cnt[self.heap[0]] -= 1
            heappop(self.heap)

    

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        left = LazyHeap()
        right = LazyHeap()

        n = len(nums)
        ans = [0] * (n-k+1)
        for i, x in enumerate(nums):
            if left.size <= right.size:
                left.push(-right.pushpop(x))
            else:
                right.push(-left.pushpop(-x))
            
            if i < k-1:
                continue
            
            if k % 2 == 0:
                ans[i-k+1] = (-left.top() + right.top()) / 2
            else:
                ans[i-k+1] = -left.top()
            
            to_remove = nums[i-k+1]
            if to_remove > -left.top():
                right.remove(to_remove)
                if left.size > right.size + 1:
                    right.push(-left.pop())
            else:
                left.remove(-to_remove)
                if left.size < right.size:
                    left.push(-right.pop())
        return ans