1
import heapq
2
from collections import defaultdict
3

4

5
class Solution:
6
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
7
        if not nums or not k:
8
            return []
9
        lo = []  # max heap
10
        hi = []  # min heap
11
        for i in range(k):
12
            if len(lo) == len(hi):
13
                heapq.heappush(hi, -heapq.heappushpop(lo, -nums[i]))
14
            else:
15
                heapq.heappush(lo, -heapq.heappushpop(hi, nums[i]))
16
        ans = [float(hi[0])] if k & 1 else [(hi[0] - lo[0]) / 2.0]
17
        to_remove = defaultdict(int)
18
        for i in range(k, len(nums)):  # right bound of window
19
            heapq.heappush(lo, -heapq.heappushpop(hi, nums[i]))  # always push to lo
20
            out_num = nums[i - k]
21
            if out_num > -lo[0]:
22
                heapq.heappush(hi, -heapq.heappop(lo))
23
            to_remove[out_num] += 1
24
            while lo and to_remove[-lo[0]]:
25
                to_remove[-lo[0]] -= 1
26
                heapq.heappop(lo)
27
            while to_remove[hi[0]]:
28
                to_remove[hi[0]] -= 1
29
                heapq.heappop(hi)
30
            if k % 2:
31
                ans.append(float(hi[0]))
32
            else:
33
                ans.append((hi[0] - lo[0]) / 2.0)
34
        return ans