> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/15_tree_map/480.-sliding-window-median.md).

# 480. Sliding Window Median

<https://leetcode.com/problems/sliding-window-median/>

## solution

```python
# 类似于81题数据流的中位数，两个堆，一个大根堆维护中位数以左的，一个小根堆维护中位数以右的元素

from bisect import insort, bisect_left

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        ans = []
        window = sorted(nums[:k])  # 排序

        def get_median(window, k):
            return (window[(k - 1) // 2] + window[k // 2]) / 2.0

        ans.append(get_median(window, k))

        for i in range(k, len(nums)):
            index = bisect_left(window, nums[i - k])  # 即将移出窗口的元素，其他的仍然排序
            window.pop(index)

            insort(window, nums[i])
            ans.append(get_median(window, k))

        return ans
```

时间复杂度：O(n x k)\
空间复杂度：O(n)

## follow up

[295. Find Median from Data Stream](/mle-interview/01_leetcode/06_heap/295.-find-median-from-data-stream.md)