“数据流的中位数”这五个字在准备面试的人眼里基本等同于“优先队列双堆”四个字。它被问到的频率高得吓人但每次真到面试现场能一次性写对的人并不多。这道题在力扣上的热度常年排在前列因为它干脆利落地考察了一个关键能力面对一个永远在变大的数据集合你能不能设计出一种结构让“插入”和“取中位数”都保持高效。这篇文章我直接给你搭好完整骨架从题目拆解、双堆原理、代码模板到我在提交和面试中踩过的坑以及它背后的一整套扩展题型。适合正在刷力扣准备面试的朋友也适合工作中要写实时统计逻辑的工程师只要你会用优先队列这篇吃透问题不大。题干本身并不复杂设计一个类支持addNum(int num)把数字加入数据流支持findMedian()返回当前所有数字的中位数。奇数个取中间那个偶数个取中间两个的平均值。真正的复杂度来源于“数据流”三个字——数据不是一次性给你而是持续到达而且你永远不知道下一个数有多大、总数会有多少。1. 先把题目读透数据流中位数的真正难点1.1 题号乌龙76题还是295题先说个很多人在评论区吵过的话题你搜“力扣第76题 数据流的中位数”往往会看到两种说法打架。实际上力扣题库里第76题是“最小覆盖子串”数据流的中位数是第295题。题号记混太常见了网上讨论帖里也经常看到但好在这题无论挂在哪个编号下面核心思路都不变照刷就行。题目要求实现的接口就两个。addNum是写操作负责把新数接收进来findMedian是读操作负责返回当前所有接收数字的中位数。比如依次加入 1、2此刻中位数是 1.5再加入 3中位数变成 2。注意中位数和平均数不是一回事数据流里出现极端大值 100 也不会改变中位数指向中间位置的本质这是后面设计算法的根。很多第一次刷的人觉得“这不就是维护一个有序数组吗”但在力扣的评测环境下数据流的长度可以到 10 万甚至更大操作总次数也会卡到高位。一旦你插入一个数就做一次全排序基本就是超时预定。要意识到一个问题算法题里的“数据流”三个字天然暗示了两个约束——数据按时间逐步到达以及查询可能在任意时刻发生。1.2 朴素思路能撑多久先看几个最直接的方案你就能明白为什么这题值得单独写一篇。第一种每次findMedian的时候把当前所有元素复制出来排个序取中间。插入是 O(1)但每次查询是 O(n log n)。如果查询频率高比如在数据流中交替插入和查询 n 次总复杂度会变成 O(n² log n)。n 到 10 万这个量级计算量是天文学数字。第二种维护一个始终有序的数组。插入的时候二分找到位置然后vector.insert把后面的元素整体后移。插入 O(n)查询 O(1)因为直接按下标访问即可。看起来好一点但插入时要移动元素数据量大起来依然扛不住。而且insert在中间位置频繁触发时内存拷贝也非常伤性能。第三种用平衡树TreeMap、multiset维护有序集合。插入 O(log n)但找中位数需要知道中间那个元素是谁而平衡树的迭代器前进是 O(log n) 或至少不是 O(1)实现还复杂。这是个可行方向但不是最优解。三种方案摆在一起你会发现共同的痛点它们要么在维护“完整的全局有序序列”要么在查询时重新排序。可中位数真的需要全局有序吗其实不需要这就是突破口。1.3 中位数真正在意的只有两个点把任意一组有序数排好切成两半。中位数本质上就是“左半边的最大值”和“右半边的最小值”这两个点的函数。奇数个元素时中间那个就是左半边的最大值偶数个元素时中位数是左半边最大值和右半边最小值的平均数。换句话说你根本不需要知道左半边内部 1、2、3 谁先谁后只需要知道左半边最大的数是多少也不需要知道右半边 7、8、9 的内部顺序只需要知道右半边最小的数是多少。这个认知是整道题的核心也是为什么答案会选择堆而不是数组或树的根本原因——堆的建立成本低插入 O(log n)取堆顶 O(1)正好能应付你只想快速拿极值的需求。打一个生活比方班里有 30 个人按身高排队你要找中位身高只需要把队伍分成左右两堆记住左堆最高的人和右堆最矮的人就够了。至于左堆里第二高是谁右堆里第二矮是谁跟你的目标一点关系都没有。双堆方案就是把这个生活直觉翻译成了代码用两个堆分别记住这两个关键人物。2. 双堆方案为什么偏偏是最大堆加最小堆2.1 为什么数组不行堆可以数组的问题是插入成本太高。有序数组要维护顺序插入一个数往往要挪动一片元素无序数组查询中位数又得重新排序。堆不一样堆的插入和删除堆顶都是 O(log n)而且永远能在 O(1) 时间内告诉你当前极值。这里要打破一个常见误区很多人以为堆就是“排好序的树”不是。堆只保证父节点和子节点之间的顺序不保证兄弟节点之间有序。正是这种“局部有序”让它效率高也正是这种特性让它没法做全局查询。可我们用两个堆一个从头往中间挤一个从尾往中间挤所需要的“中间分界线”刚好就是两个堆顶完美避开堆的短板。具体分工是最大堆左边存所有元素里较小的一半堆顶是这一半的最大值最小堆右边存较大的一半堆顶是这一半的最小值。只要保证左边堆顶小于等于右边堆顶并且两边数量差距不超过 1那么中位数就一定是左边堆顶或者左边堆顶和右边堆顶的平均数。2.2 两条核心约束与一套固定流程双堆方案要正常工作必须同时满足两个约束。第一是有序性约束左堆所有元素都必须小于等于右堆所有元素等价于左堆堆顶 右堆堆顶。否则左右两半就交叉了两个堆顶也没法代表中间位置。第二是平衡性约束左堆和右堆的大小差不能超过 1。我习惯让左堆永远不小于右堆也就是左堆要么比右堆多一个要么两边相等。这样在元素总数为奇数时中位数就是左堆堆顶总数为偶数时中位数才是两个堆顶的平均。对应实现业内最流行也最不容易出错的模板是三步走新元素一律先塞进左堆。立刻把左堆的堆顶也就是当前所有元素中的最大值弹出来塞进右堆。检查左堆大小是否小于右堆大小如果是就把右堆的堆顶弹回左堆。第一步是无条件接收第二步是把“过大的元素”分流到右堆完成有序性修正第三步是平衡性修正。这套流程最妙的地方在于它不需要在插入前比较新数和堆顶的大小避免了大量边界条件判断。你只管执行三步堆会自动把大小顺序调好。我强烈建议你直接用这个模板不要自己发明“先比较再插入”的写法后者几乎每次都会漏掉一种边界情况。2.3 手动模拟一次完整数据流光讲理论不够我拿一个真实序列走一遍依次加入 5、2、8、4、7。约定左堆是最大堆堆顶最大右堆是最小堆堆顶最小。操作左堆内容最大堆堆顶在前右堆内容最小堆堆顶在前当前中位数addNum(5)[5][]5addNum(2)[2][5]3.5addNum(8)[5, 2][8]5addNum(4)[4, 2][5, 8]4.5addNum(7)[5, 4, 2][7, 8]5一步步看。先加 5左堆一个元素中位数是 5。加 2 时如果只按先后顺序想应该左边存 2、右边存 5这样左堆最大值 2右堆最小值 5中位数 (25)/23.5对应序列 [2,5] 的中位数。加 8 是关键步骤。8 是当前最大左堆拿到 8 后第二步会把左堆堆顶此时是 8移到右堆左堆剩 [2]右堆是 [5,8]。然后第三步看到左堆比右堆少把右堆堆顶 5 弹回左堆最终左堆 [5,2]右堆 [8]即左边存较小一半 [2,5]右边存较大一半 [8]中位数 5。整个过程没有一次比较大小全靠堆顶自动流转。加 4 和加 7 同理你可以用同样的三步走自己在纸上画一遍。重点观察每行左右堆元素数量差始终是 0 或 1而且左堆所有元素永远小于右堆所有元素。画出这一张表你就彻底理解双堆了后面代码基本是水到渠成。3. 一版最稳的代码模板与实现细节3.1 可复制的 C 与 Python 实现代码直接用上面说的三步走模板。C 里priority_queue默认是最大堆所以左堆直接声明右堆需要传greaterint变成最小堆。class MedianFinder { public: priority_queueint left; // 最大堆存较小的一半 priority_queueint, vectorint, greaterint right; // 最小堆存较大的一半 MedianFinder() {} void addNum(int num) { left.push(num); right.push(left.top()); left.pop(); if (left.size() right.size()) { left.push(right.top()); right.pop(); } } double findMedian() { if (left.size() right.size()) return left.top(); return (left.top() right.top()) / 2.0; } };Python 里heapq只有最小堆想要最大堆就把元素取负数再入堆取堆顶时再取负还原。这个技巧如果你第一次见建议花几秒理解一下堆默认按从小到大排负数之后原来大的数在堆里反而“小”了堆顶就成了原来最大的数完美模拟最大堆。import heapq class MedianFinder: def __init__(self): self.left [] # 最大堆存负数 self.right [] # 最小堆 def addNum(self, num: int) - None: heapq.heappush(self.left, -num) heapq.heappush(self.right, -heapq.heappop(self.left)) if len(self.left) len(self.right): heapq.heappush(self.left, -heapq.heappop(self.right)) def findMedian(self) - float: if len(self.left) len(self.right): return -self.left[0] return (-self.left[0] self.right[0]) / 2.0两份代码逻辑完全一致。C 版的left.pop()是无返回值的所以要把left.top()传给右堆必须分两步写不能像 Python 那样在参数里直接调heappop。这是语言差异不是思路差异。3.2 三个语言层面的细节坑第一个坑在 C。priority_queue的pop()返回void你想把堆顶挪到另一个堆必须写int tmp left.top(); left.pop(); right.push(tmp);。新手容易手滑写成right.push(left.pop())编译直接报错。第二个坑在 Python。你往left里存的是负数取堆顶时一定要-self.left[0]。我见过有人findMedian里直接返回self.left[0]测试数据全是负值还奇怪为什么结果对不上。堆顶负数取反这一步是 Python 版最容易错的地方。第三个坑涉及所有语言偶数情况下一定要除以2.0不能除以2。5 / 2在 C 和 Java 里结果是整数 2不是 2.5。力扣的测试用例会专门卡这一点返回值类型是double你写2也会通过编译但结果错得毫无悬念。Java 版如果面试需要也顺手给一个参考。PriorityQueue默认最小堆最大堆用Collections.reverseOrder()class MedianFinder { PriorityQueueInteger left; PriorityQueueInteger right; public MedianFinder() { left new PriorityQueue(Collections.reverseOrder()); right new PriorityQueue(); } public void addNum(int num) { left.add(num); right.add(left.poll()); if (left.size() right.size()) { left.add(right.poll()); } } public double findMedian() { if (left.size() right.size()) return left.peek(); return (left.peek() right.peek()) / 2.0; } }3.3 时间和空间复杂度为什么值得addNum做了有限的几次堆操作每次 push 或 pop 都是 O(log n)所以整体 O(log n)。findMedian只是看两个堆顶O(1)。空间上需要把全部数据存进堆O(n)。对比一下三种方案方案插入取中位数空间每次查询排序O(1)O(n log n)O(n)有序数组O(n)O(1)O(n)双堆O(log n)O(1)O(n)双堆方案不是把复杂度降到魔法级别而是把复杂度均匀摊到了每次插入上。数据流场景里插入和查询都可能高频发生任何一头太重都会拖垮整体性能。O(log n) 的插入配合 O(1) 的查询恰好是工程里最舒服的平衡点。4. 我踩过的坑常见问题与排查实录4.1 奇偶状态混乱中位数取错这题最常见的失误就是在左右堆的奇偶关系上翻车。症状表现是总数为奇数时结果对偶数时偏了一个或者反过来。原因很简单左右堆大小关系没有保持稳定。我自己早期写的版本喜欢在插入前判断总数奇偶然后决定往哪个堆放结果每加一个数就要改一次逻辑改着改着就把平衡条件忘了。后来换成了“先左后右再平衡”的固定模板奇偶问题彻底消失因为模板每一步都在修正平衡关系你根本不需要关心当前总数是奇还是偶。如果你正在排查自己的代码一个很有效的技巧是在addNum末尾打印left.size()和right.size()再打印两个堆顶。只要发现某一步左右差大于 1或者左堆顶大于右堆顶问题就锁定了。用手动模拟法推三四个数比看半天代码管用得多。4.2 堆顶比较和空数据的边界处理看题时注意一个小细节题目一般保证findMedian不会在空数据流上调用但面试官可能会口头追问。空堆调用top()是未定义行为轻则崩溃重则返回垃圾值。稳妥的做法是在findMedian开头判断一下堆是否为空空则抛出异常或返回一个约定的哨兵值。重复元素也是一个容易忽视的边界。数据流里会出现大量相同的数比如全是 5。堆天然支持重复元素三步走模板不会乱。但如果你自己写了“比较后插入”的逻辑就要小心和的使用口径必须一致。一会儿用判断放左堆一会儿用相同元素的分布就会漂移堆顶可能不符合预期。用固定模板就没这个问题。还有一个细节是极端值相加溢出。左右堆顶分别是INT_MIN和INT_MAX时两者相加在 int 范围内直接溢出。我的习惯是先转成long long再相加最后除以2.0分母写成浮点数还能顺带解决整数除法问题。4.3 面试官常问的三个追问面试官出这题通常不会只让写完代码就结束后面跟着的追问才是真正的考卷。第一个追问为什么不用平衡树我一般这样回答平衡树能维护全局有序序列插入也是 O(log n)但要取得中位数还得移动迭代器而且红黑树之类的实现复杂度、常数都远高于堆。双堆只关心两个极值职责单一代码短更合适。第二个追问能不能做到 O(1) 插入这个问题有点陷阱。如果数据范围有限制比如数值固定分布在 0 到 100可以用计数桶做到 O(1) 插入和 O(1) 查询。如果数据范围无限比较排序下界决定了不可能做到。我会先回答“在数据范围有限时可以”再补充一句“否则没有已知方案”显得思路完整。第三个追问数据量大到内存放不下怎么办面试官希望看到你能意识到堆把所有数据都存下来了空间 O(n)。可以聊抽样、分桶、近似分位数算法比如 T-digest 这些工程方案。这已经超出算法题本身的范围但能把话题引向系统设计属于加分项。5. 进阶扩展从一道题到一类题5.1 数据范围有限桶计数方案面试追问里提到的“数据范围有限”到底怎么做假设数值是 0 到 100 的考试分数你可以开一个长度 101 的计数数组每个值出现一次就把对应桶加一。插入是 O(1)查中位数时从头往后累加计数找到第 n/2 个元素的位置就行。因为桶大小固定遍历 101 次也算是 O(1)。代码示意class MedianFinder: def __init__(self): self.count [0] * 101 self.total 0 def addNum(self, num: int) - None: self.count[num] 1 self.total 1 def findMedian(self) - float: cnt 0 for i in range(101): cnt self.count[i] if cnt (self.total - 1) // 2: break low i cnt 0 for i in range(101): cnt self.count[i] if cnt self.total // 2: break high i return (low high) / 2.0这个方案的时间复杂度比双堆更好但它强依赖“数值范围有限”这个前提。如果数据范围是 0 到 2³¹开一个 20 亿长度的数组内存先爆了。所以双堆才是通用解桶计数是特化解。5.2 双堆思路的同类题扩展理解双堆之后很多题都会变得顺手。力扣 480 题“滑动窗口中位数”就是双堆的进阶版它要求窗口在数组上滑动动态维护窗口内元素的中位数。除了双堆还得处理过期元素业界常用“惰性删除”——元素还在堆里但用一个延迟删除标记记录下来等它到堆顶时再真正弹出。思路还是“两个堆夹住中间”只是多了一层窗口过期管理。力扣 703 题“数据流中的第 K 大元素”是双堆的简化版只需要维护一个大小为 K 的最小堆堆顶就是答案。力扣 692 题“前 K 个高频单词”也用堆只是比较器从数值变成了词频加字典序。你会发现只要看到“动态数据里取第 K 个”“动态数据里取中位数”第一反应都应该是堆的方向。5.3 刷题攻略里的定位与练习顺序在力扣刷题攻略里这题属于“数据结构设计”类和 LRU 缓存、实现栈这些题并列。我的建议是安排在堆专题的中段再刷先做 215 题“数组中的第 K 个最大元素”熟悉堆的 API 和顶堆的直觉再做 347 题“前 K 个高频元素”理解堆和哈希表的配合然后做 703 题理解固定大小堆最后做 295 题这里才引入双堆概念。顺序对了会觉得一路升级都很自然。写完这道题之后我还有一个习惯性的收尾动作不看任何参考自己在纸上模拟一个 15 个数字的插入序列每一步写下左右堆的元素变化。这比反复看十遍代码都有用。因为双堆的每一步流程是固定的本质上就是一个状态机你只要把状态转移的节奏刻进脑子里一个月后再写也能一次通过。刷题这件事最难的不是背代码而是建立一个足够稳定的直觉。这题正好能训练这件事。我以前第一次刷时总觉得“先左后右再平衡”的写法很玄乎直到在纸上画了十几个数的堆交换才彻底明白原来每次 addNum 不过是在左堆塞一个、向右边漂一个、必要时再捞回来。想通了它后面同类题型基本就是套模板心里完全不慌。空闲的时候你也可以试试用不同的语言反复写这题C 写一遍Python 写一遍Java 再写一遍每次都能发现语言特性对同一逻辑的不同表达方式。半年之后回来看你会发现自己对堆和数据结构设计这件事的理解已经完全不一样了。
