题目描述
设计一个结构，支持 addNum(x) 不断加数、findMedian() 随时返回当前所有数的中位数。
思路解析
数一直在来，每问一次就重新排序，查得越频繁越崩。我们要的是「随时 O(1) 拿到中位数」，又不想每次重排——这正是要优化掉的浪费。
转折：中位数只跟「最中间那一两个数」有关，何必排好全部？用大顶堆 small 装较小一半（堆顶=这半的最大值）、小顶堆 large 装较大一半（堆顶=那半的最小值）。中位数永远卡在这两个堆顶上，拿它 O(1)。
维持两条规则：① small 里每个数 ≤ large 里每个数；② 本实现约定 small 的个数必须等于 large、或恰好比它多 1（即 len(small) − len(large) ∈ {0, 1}）。所以「small 多 2」或「large 比 small 多」都算失衡，要挪一个堆顶过去。奇数个时中位数 = small 堆顶；偶数个时 = 两堆顶平均。下面逐个加 5、3、8、1。
加入 5 · 放入：第一个数 5，放进左边大顶堆 small。两堆个数差 1，已平衡，不用挪。
加入 5 · 读中位数：一共 1 个数，奇数，中位数 = 数多的那个堆顶 = small 顶 5。
加入 3 · 放入（失衡）：加入 3：它比 small 顶 5 小，进左堆。但左堆一下多了 2 个、右堆空着——失衡了，下一步要调。
加入 3 · 平衡 + 读：平衡：把 small 堆顶 5 挪到 large。现在左 [3]、右 [5] 各一个。偶数个，中位数 = 两堆顶平均 = (3+5)/2 = 4。
加入 8 · 放入（失衡）：加入 8：比 large 顶 5 大，进右堆。这回右堆多了 1 个，又失衡——往多的一边的反方向挪。
加入 8 · 平衡 + 读：平衡：把 large 堆顶（最小的）5 挪回 small。左 [3,5]、右 [8]。奇数个，中位数 = 数多的 small 顶 5。
加入 1 · 放入（失衡）：加入 1：比 small 顶小，进左堆。左堆涨到 3 个，比右堆多 2——再调一次。
加入 1 · 平衡 + 读：平衡：small 顶 5 挪到 large。左 [1,3]、右 [5,8]。四个数排序是 1,3,5,8，中间两个 3、5，中位数 = (3+5)/2 = 4。全程没有重排，每步只挪一个堆顶。
「动态求中位数 / 求第 K 大」的经典结构：一个大顶堆 + 一个小顶堆对顶，维持大小平衡，中位数永远在两个堆顶之间。
参考代码（Python）
1import heapq
2class MedianFinder:
3 def __init__(self):
4 self.small = [] # 大顶堆(存负数模拟)，较小一半
5 self.large = [] # 小顶堆，较大一半
6 def addNum(self, x):
7 heapq.heappush(self.small, -heapq.heappushpop(self.large, x))
8 if len(self.small) > len(self.large) + 1:
9 heapq.heappush(self.large, -heapq.heappop(self.small))
10 def findMedian(self):
11 if len(self.small) > len(self.large): return -self.small[0]
12 return (-self.small[0] + self.large[0]) / 2复杂度分析
- 时间复杂度：O(log n) —— addNum 每次堆插入/弹出 O(log n)；findMedian 直接读两个堆顶 O(1)
- 空间复杂度：O(n) —— 两个堆合起来存下所有 n 个数
套路模板
记住三句话：small 全员 ≤ large 全员、两堆大小差 ≤ 1、奇取多堆顶偶取平均。三条守住就对了。
1small = [] # 大顶堆(负数)，装较小一半
2large = [] # 小顶堆，装较大一半
3# 加数：保证 small 的所有数 <= large 的所有数
4# 平衡：两堆大小差 <= 1
5# 中位数：奇数取多的那堆顶，偶数取两堆顶平均易错点
- 错误写法：大顶堆、小顶堆装反（small 装大的） → 正确写法：small 装较小一半、large 装较大一半（装反了堆顶就不是中间值，中位数全错）
- 错误写法：只入堆不平衡 → 正确写法：每次 addNum 后检查并调平两堆大小（不平衡的话「中间」会偏到一边，堆顶不再是中位数）
- 错误写法：Python 直接用 heapq 当大顶堆 → 正确写法：存相反数模拟大顶堆（heapq 只有小顶堆，装较小一半要靠存负数来「翻转」）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。