题目描述
设计一个结构，支持 addNum(x) 不断加数、findMedian() 随时返回当前所有数的中位数。
依次加入 = 5, 3, 8, 1
每次中位数 = 5 → 4 → 5 → 4
思路解析
每问一次就把所有数排序，查得越频繁越崩。我们要的是「随时 O(1) 拿到中位数」。
把数据从中间劈开：左边一半用大顶堆（堆顶 = 这半里最大的），右边一半用小顶堆（堆顶 = 那半里最小的）。中位数就在这两个堆顶上。
每加一个数，先丢进合适的一边，再把两堆调平衡。奇数个时中位数 = 数多的那个堆顶；偶数个时 = 两个堆顶的平均。
加入 5：第一个数 5，放进左边的大顶堆。就一个数，中位数当然是 5。（堆顶在最右端）
加入 3：加入 3，调平衡后变成：左堆装 3、右堆装 5。两个数，中位数取两个堆顶平均 = 4。
加入 8：加入 8（较大，进右边），再平衡。左堆 [3,5]、右堆 [8]，奇数个，中位数 = 数多的左堆顶 5。
加入 1：加入 1（较小，进左边），平衡后左堆 [1,3]、右堆 [5,8]。四个数 5,3,8,1 排序是 1,3,5,8，中间两个 3、5，中位数 = 平均 4。
「动态求中位数 / 求第 K 大」的经典结构：一个大顶堆 + 一个小顶堆对顶，维持大小平衡，中位数永远在两个堆顶之间。
参考代码（Python）
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复杂度分析
- addNum：O(log n) —— 堆的插入/弹出
- findMedian：O(1) —— 直接读两个堆顶
套路模板
记住三句话：small 全员 ≤ large 全员、两堆大小差 ≤ 1、奇取多堆顶偶取平均。三条守住就对了。
Python
1small = [] # 大顶堆(负数)，装较小一半
2large = [] # 小顶堆，装较大一半
3# 加数：保证 small 的所有数 <= large 的所有数
4# 平衡：两堆大小差 <= 1
5# 中位数：奇数取多的那堆顶，偶数取两堆顶平均易错点
- ❌ 大顶堆、小顶堆装反（small 装大的） → ✅ small 装较小一半、large 装较大一半（装反了堆顶就不是中间值，中位数全错）
- ❌ 只入堆不平衡 → ✅ 每次 addNum 后检查并调平两堆大小（不平衡的话「中间」会偏到一边，堆顶不再是中位数）
- ❌ Python 直接用 heapq 当大顶堆 → ✅ 存相反数模拟大顶堆（heapq 只有小顶堆，装较小一半要靠存负数来「翻转」）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。