原题地址（困难）

方法1—优先队列/堆

思路

这题真的太难了

这题是在295题基础之上，难度我感觉又提升了一个level
295. 数据流的中位数
295题是单纯的双优先队列，而这题，又加了 延迟删除 的思想，这是最难的地方。
直接看了官方题解，照着它的思路写了代码。

代码

  1. class DualHeap:
  2.     def __init__(self, k: int):
  3.         self.maxHeap = []
  4.         self.minHeap = []
  5.         self.delayed = collections.Counter()
  6.         self.k = k
  7.         self.maxHeapSize = 0
  8.         self.minHeapSize = 0
  10.     def prune(self, heap):  # 不断删除堆顶元素，更新哈希表，为的是保证堆顶元素是不需要被延迟删除的
  11.         while heap:
  12.             num = heap[0]  # 堆顶元素
  13.             if heap is self.maxHeap:  # 大顶堆要取反
  14.                 num = -num
  15.             if num in self.delayed:   # 这个堆顶元素需要删除
  16.                 self.delayed[num] -= 1
  17.                 if self.delayed[num] == 0:
  18.                     self.delayed.pop(num)
  19.                 heapq.heappop(heap)
  20.             else:
  21.                 break
  23.     def makeBalance(self): # 调整大根堆小根堆的元素个数
  24.         if self.maxHeapSize - self.minHeapSize >= 2:
  25.             maxHeapTop = -heapq.heappop(self.maxHeap) # 得到堆顶元素
  26.             heapq.heappush(self.minHeap, maxHeapTop)  # 放入小顶堆
  27.             self.maxHeapSize -= 1
  28.             self.minHeapSize += 1
  29.             self.prune(self.maxHeap)
  30.         elif self.minHeapSize > self.maxHeapSize:
  31.             minHeapTop = heapq.heappop(self.minHeap)
  32.             heapq.heappush(self.maxHeap, -minHeapTop)
  33.             self.minHeapSize -= 1
  34.             self.maxHeapSize += 1
  35.             self.prune(self.minHeap)
  37.     def insert(self, num): # 插入
  38.         if not self.maxHeap or num <= -self.maxHeap[0]:
  39.             heapq.heappush(self.maxHeap, -num)
  40.             self.maxHeapSize += 1
  41.         else:
  42.             heapq.heappush(self.minHeap, num)
  43.             self.minHeapSize += 1
  44.         self.makeBalance()
  46.     def erase(self, num):  # 删除
  47.         self.delayed[num] += 1
  48.         if num <= -self.maxHeap[0]:
  49.             self.maxHeapSize -= 1
  50.             if num == -self.maxHeap[0]:
  51.                 self.prune(self.maxHeap)
  52.         else:
  53.             self.minHeapSize -= 1
  54.             if num == self.minHeap[0]:
  55.                 self.prune(self.minHeap)
  56.         self.makeBalance()          
  58.     def getMedian(self):  # 得到中位数
  59.         return -self.maxHeap[0] if self.k & 1 else (-self.maxHeap[0] + self.minHeap[0]) / 2
  62. class Solution:
  63.     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
  64.         dh = DualHeap(k)
  65.         for num in nums[:k]: # 初始化
  66.             dh.insert(num)
  67.         ans = [dh.getMedian()]
  68.         for i in range(k, len(nums)):
  69.             dh.insert(nums[i])
  70.             dh.erase(nums[i-k])
  71.             ans.append(dh.getMedian())
  72.         return ans

时空复杂度

时间复杂度O(logN)
空间复杂度O(N)