题目描述
思路解析动画文字版
记住这句:小的一半放大顶堆 small、大的一半放小顶堆 large,让 small 和 large 等大、或 small 多一个。k 奇数时中位数是 small 堆顶,k 偶数时取 small 顶和 large 顶的平均,都是 O(1) 读到。
先把第 0 个窗口建起来。第一个数 1 进 small(大顶堆),现在 small 堆顶是 1,large 还空着。
来第二个数 3。它比 small 堆顶 1 大,属于「较大的一半」,放进 large(小顶堆)。现在两边各一个,small 顶 1、large 顶 3。
第三个数 -1,它 < small 堆顶 1,属于「较小的一半」,进 small。这下 small 有 2 个、large 有 1 个,small 比 large 多一个,正好符合不变量,不用再平衡。
第 0 个窗口 [1, 3, -1] 就位:small 装较小的一半、堆顶是 1,large 装较大的一半。k 是奇数,中位数就是 small 堆顶 1。答案数组:[1]。
窗口右滑一格:离开窗口的是左边的 1,新进来的是右边的 -3。先把 1 从它所在的堆删掉,再把 -3 放进 small(它不大于 small 堆顶)。此刻 small 有 2 个、large 有 1 个。
检查两堆个数:small 2 个、large 1 个,已经符合 small 比 large 多 0 或 1 个,这一步不用搬动。
读 small 堆顶:-1,就是窗口 [3, -1, -3] 的中位数 -1。答案接成 [1, -1]。
窗口接着右移:离开窗口的是左边的 3,新进来的是右边的 5。先把 3 从它所在的堆删掉,再把 5 放进 large(它大于 small 堆顶)。此刻 small 有 2 个、large 有 1 个。
检查两堆个数:small 2 个、large 1 个,已经符合 small 比 large 多 0 或 1 个,这一步不用搬动。
读 small 堆顶:-1,就是窗口 [-1, -3, 5] 的中位数 -1。答案接成 [1, -1, -1]。
再滑一格:离开窗口的是左边的 -1,新进来的是右边的 3。先把 -1 从它所在的堆删掉,再把 3 放进 large(它大于 small 堆顶)。此刻 small 有 1 个、large 有 2 个。
两堆个数失衡了,做一次再平衡:large 多了一个,把 large 堆顶 3 挪到 small,直到 small 比 large 多 0 或 1 个。现在窗口 [-3, 5, 3] 的两堆排好了。
读 small 堆顶:3,就是窗口 [-3, 5, 3] 的中位数 3。答案接成 [1, -1, -1, 3]。
窗口继续右滑:离开窗口的是左边的 -3,新进来的是右边的 6。先把 -3 从它所在的堆删掉,再把 6 放进 large(它大于 small 堆顶)。此刻 small 有 1 个、large 有 2 个。
两堆个数失衡了,做一次再平衡:large 多了一个,把 large 堆顶 5 挪到 small,直到 small 比 large 多 0 或 1 个。现在窗口 [5, 3, 6] 的两堆排好了。
读 small 堆顶:5,就是窗口 [5, 3, 6] 的中位数 5。答案接成 [1, -1, -1, 3, 5]。
最后滑一格:离开窗口的是左边的 5,新进来的是右边的 7。先把 5 从它所在的堆删掉,再把 7 放进 large(它大于 small 堆顶)。此刻 small 有 1 个、large 有 2 个。
两堆个数失衡了,做一次再平衡:large 多了一个,把 large 堆顶 6 挪到 small,直到 small 比 large 多 0 或 1 个。现在窗口 [3, 6, 7] 的两堆排好了。
读 small 堆顶:6,就是窗口 [3, 6, 7] 的中位数 6。答案接成 [1, -1, -1, 3, 5, 6]。
六个窗口全部滑完,中位数依次是 [1, -1, -1, 3, 5, 6],和开头说的一致。回头看:每个窗口我们都没有重新排序,只靠「加一个、删一个、平衡一下、读堆顶」就拿到了中位数,每步只是常数次堆/有序集合操作(具体复杂度按实现区分,见下一页)。
k=1 即自身、k 偶取两顶平均(小数)、有负数照常,这些边界想清就稳。
两个高频追问:为什么用两个堆、怎么保证堆顶是中位数。
参考代码
from typing import Listimport heapqfrom collections import defaultdictclass Solution: def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: small, large = [], [] delayed = defaultdict(int) small_size = large_size = 0 def prune(heap): while heap: x = -heap[0] if heap is small else heap[0] if delayed[x]: delayed[x] -= 1 heapq.heappop(heap) else: break def balance(): nonlocal small_size, large_size if small_size > large_size + 1: heapq.heappush(large, -heapq.heappop(small)) small_size -= 1; large_size += 1 prune(small) elif small_size < large_size: heapq.heappush(small, -heapq.heappop(large)) small_size += 1; large_size -= 1 prune(large) def add(x): nonlocal small_size, large_size if not small or x <= -small[0]: heapq.heappush(small, -x); small_size += 1 else: heapq.heappush(large, x); large_size += 1 balance() def remove(x): nonlocal small_size, large_size delayed[x] += 1 if x <= -small[0]: small_size -= 1 if x == -small[0]: prune(small) else: large_size -= 1 if large and x == large[0]: prune(large) balance() def median(): return float(-small[0]) if k % 2 else (-small[0] + large[0]) / 2.0 ans = [] for i, x in enumerate(nums): add(x) if i >= k: remove(nums[i - k]) if i >= k - 1: ans.append(median()) return ans复杂度
- 时间：O(n log k) / O(n log n)，C++/Java 两个有序集合:插入/删除/取边界各 O(log k) → O(n log k);Python 对顶堆 + 纯延迟删除不重建,失效元素堆积、最坏退化到 O(n log n)(实践多接近 O(n log k))
- 空间：O(k) / O(n)，C++/Java 有序集合只存窗口 k 个 → O(k);Python 延迟删除会暂存失效元素,最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么要两个堆,一个不行吗?
追问怎么保证 small 堆顶始终是中位数?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
K 个不同整数的子数组
LeetCode 992 · 困难 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题