力扣第76题“数据流的中位数”这道题我刷了三遍才敢说真正吃透了它。初次见面觉得是个简单题仔细一看是个经典设计题再往深处挖它背后藏着的“动态维护TopK”“双堆对冲”“大小根堆平衡”这些思想几乎贯穿你后面会碰到的所有高级数据结构题。这篇文章我不打算对着题解说题而是把我自己从“背模板”到“理解原理”再到“在面试和业务里用到”的完整经历写出来把这道题从题目到实战的每一层窗户纸都捅破。这道题解决的核心问题很朴素一个数据流不断读入数据随时需要你能取出当前所有数据的中位数。传统思路是插进去再排序或者读的时候现排但数据流源源不断效率根本扛不住。适合所有正在备战面试、需要系统地搞定堆相关题型的读者也适合那些工作中要处理实时监控指标、需要快速计算分位数的工程同学。读完之后你会发现双堆玩法不只是解这一道题的钥匙而是一类方案的通关密码。1. 题目拆解与思路定位1.1 先搞清楚题到底在问什么力扣把这题编号为第76题在LeetCode原题体系里面对应的是第295题。题面特别短设计一个支持两种操作的数据结构一种是往结构里添加一个整数另一种是返回当前所有元素的中位数。这里有个非常容易踩的坑题目说的是数据流不是静态数组。静态数组里找中位数先排序再取中间位置复杂度O(n log n)一次搞定但数据流场景下元素是不断追加的每次查询都必须基于当前全部数据。你如果用数组存储每次查询先拷贝一份再排序数据量一大必死无疑。我一开始犯过这个错心想“这不就是个排序取中嘛”结果当场被驳了回来。面试官问了一句“如果有一百万个数据持续流入每次查询都O(n log n)全量排序你扛得住吗” 我一下沉默了。这题的约束条件也很关键最多调用5 x 10^4次addNum和findMedian数据范围是Java标准int范围可能为负数也可能有重复值。进阶要求里明确指出如果数据流中大部分整数落在某个区间内如何优化——这是给你引入计数排序桶方案做铺垫的。这些细节直接决定了你后续选型的优先级。1.2 常见思路对比为什么最终选了双堆我见过不少解法真正常见的就那么几类我逐个说下它们的定位和适用场景。第一种是有序数组二分插入。用一个ArrayList存数据每次addNum做二分查找找出插入位置然后System.arraycopy挪动元素。插入复杂度O(n)查询O(1)。这个方案对小数据量没问题但5万次调用最坏情况下数组挪动总代价是O(n²)不用测都知道会超时。第二种是桶计数方案。利用题目进阶条件“大部分整数集中在某个区间”设一个桶数组统计区间内每个数出现的次数外加两个小变量记录区间外的极小值集合和极大值集合。这个方案在特定分布下快得离谱O(1)级别插入但通用性差。你想想如果数据是随机分布在-10^9到10^9之间桶的规模根本开不出来。第三种是平衡二叉搜索树比如TreeMap维护数值和出现次数。插入O(log n)查询O(log n)。没错复杂度理论上是完全达标的但实现起来要自己维护左子树大小或者做中序定位代码量大手写时容易出边界bug。第四种就是双堆方案也是推荐答案。一个大根堆存左半边数据一个小根堆存右半边数据插入O(log n)查询中位数O(1)。代码量少思路直观不容易出边界问题。我把这四种方案列个表格对比一下方案插入复杂度查询复杂度代码量适用场景排序后取中位O(n log n)O(1)需提前全量极小静态数据有序数组二分插入O(n)O(1)小数据量小且查询频繁桶计数O(1)O(1)中数据范围集中TreeMapO(log n)O(log n)大需要同时做范围查询双堆O(log n)O(1)小动态数据流通用场景双堆不是随便选的。它最妙的地方是把“中位数”这种位置敏感的信息转化成了两个堆顶的简单比较。大根堆堆顶是左半边的最大值小根堆堆顶是右半边的最小值中位数被“夹”在二者之间。数据量奇数时其中一个堆的堆顶就是中位数偶数时两个堆顶取平均。2. 核心解法双堆如何实现中位数2.1 大小堆的分工原理把当前所有已读入的数想象成一条有序序列我们不需要记住每一个数的精确位置只需要把这条序列切成两段左边一段全部小于等于右边一段。这里有个关键点左半段用大根堆存储堆顶永远是左半段里最大的数右半段用小根堆存储堆顶永远是右半段里最小的数。为什么左边要用大根堆右边要用小根堆你可以这样理解中位数正好是这两段的“分界线”。左边一堆人里最高个儿的和右边一堆人里最矮个儿的它们俩中间就是整条序列的中间位置。假如数据总数是奇数那多出来的那个数无论放在哪一边它的堆顶就是中位数本身假如是偶数两个堆顶加一起除以二就是中位数。维持平衡的规则只有一个两个堆的元素个数差不能超过1并且左堆的元素个数只能等于右堆的元素个数或多1。我习惯固定让左堆大根堆承载多出的那个元素。原因后面会讲这能让代码里交换元素的操作有统一规则不容易写错。举个例子。假设数据流依次进入[5, 3, 1, 4, 2]。插入5左堆空直接进左堆。左堆[5]右堆[]左边多1个中位数左堆顶5。插入33小于等于左堆顶5进左堆。左堆[5,3]大根堆顶5右堆[]此时左堆比右堆多2个失衡。把左堆顶5移入右堆左堆[3]右堆[5]。两堆相等中位数(35)/24。插入11小于等于左堆顶3进左堆。左堆[3,1]右堆[5]左边多1中位数3。插入44大于左堆顶3进右堆。左堆[3,1]右堆[4,5]。左边等于右边中位数(34)/23.5。插入22小于等于左堆顶3进左堆。左堆[3,2,1]右堆[4,5]左边比右边多2把左堆顶3移入右堆。左堆[2,1]右堆[3,4,5]左边少1个不符合“左边不小于右边”的约定这里就暴露了一个问题。2.2 插入平衡逻辑与细节修正上面的例子走到最后一步时左边变成2个元素右边变成3个元素左边比右边少1个。按照固定“左堆多一个”的约定这不算严格失衡中位数此时应该是右堆顶3计算结果还是对的。但这种“左边偶尔少一个”的摇摆写法会让代码逻辑变得复杂而且容易在边界判断上出bug。更好的做法是严格保证左堆元素个数 右堆元素个数并且差值最多为1。每次插入后做一次统一调整规则如下addNum(num): if 左堆为空 或 num 左堆顶: 将 num 插入左堆 else: 将 num 插入右堆 # 平衡保证左堆数量 右堆数量且差不大于1 if 左堆.size() 右堆.size(): 将 右堆顶 移到 左堆 elif 左堆.size() - 右堆.size() 1: 将 左堆顶 移到 右堆注意上面例子的最后一步插入2后左堆[2,1]右堆[3,4,5]左堆.size() 右堆.size()因此把右堆顶3移到左堆。此时左堆[3,2,1]右堆[4,5]左堆比右堆多1中位数左堆顶3。结果是正确的。这个统一规则的背后逻辑是每插入一个数先按它和左堆顶的比较决定去左边还是右边然后立刻检查左右大小关系做一次单向搬运。因为每次最多只有一个堆超出一个元素所以每次最多只需搬一个不会产生连锁调整。还有一个小细节插入时判断条件为什么用“num 左堆顶”而不是“num 左堆顶”这涉及到相等元素如何处理。如果等于左堆顶时进了右堆右堆立刻可能比左堆多又要搬回来徒增操作。让相等的数优先去左边能减少不必要的搬运同时维护 “左堆元素右堆”的稳定性。2.3 中位数怎么取查询中位数的逻辑依赖于两个堆的元素个数关系如果左堆.size() 右堆.size()中位数 (左堆顶 右堆顶) / 2.0如果左堆.size() 右堆.size()中位数 左堆顶这里要注意返回类型。题目要求返回double如果你把两个堆顶相加再除以2整数除以整数还是整数必须强转成double。Java里可以写成(max.peek() min.peek()) / 2.0C里推荐写(maxHeap.top() minHeap.top()) / 2.0Python里直接用/就好。我在面试时最喜欢顺手说一句“查询是O(1)因为没有做任何额外计算只是看堆顶。”这句话能帮你把“为什么选双堆”的底层逻辑讲透——堆结构天然让中位数“浮”在堆顶不需要遍历。3. 手写实现与复杂度分析3.1 完整代码实现Java版我给出我自己最常用的一版实现注释都写得比较详细class MedianFinder { // 大根堆存放较小的一半数据 PriorityQueueInteger maxHeap; // 小根堆存放较大的一半数据 PriorityQueueInteger minHeap; public MedianFinder() { maxHeap new PriorityQueue((a, b) - b - a); minHeap new PriorityQueue(); } public void addNum(int num) { // 先插入到合适的堆中 if (maxHeap.isEmpty() || num maxHeap.peek()) { maxHeap.offer(num); } else { minHeap.offer(num); } // 平衡步骤保证左堆(大根堆)数量 右堆(小根堆)数量 if (maxHeap.size() minHeap.size()) { maxHeap.offer(minHeap.poll()); } else if (maxHeap.size() - minHeap.size() 1) { minHeap.offer(maxHeap.poll()); } } public double findMedian() { if (maxHeap.size() minHeap.size()) { return maxHeap.peek() * 1.0; } else { return (maxHeap.peek() minHeap.peek()) / 2.0; } } }C版本同样简洁class MedianFinder { public: priority_queueint maxHeap; // 大根堆 priority_queueint, vectorint, greaterint minHeap; // 小根堆 void addNum(int num) { if (maxHeap.empty() || num maxHeap.top()) { maxHeap.push(num); } else { minHeap.push(num); } if (maxHeap.size() minHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } else if (maxHeap.size() - minHeap.size() 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } } double findMedian() { if (maxHeap.size() minHeap.size()) { return maxHeap.top(); } return (maxHeap.top() minHeap.top()) / 2.0; } };Python版本用的是heapq默认只有小根堆大根堆用取负数法实现import heapq class MedianFinder: def __init__(self): self.min_heap [] # 存放较大的一半小根堆 self.max_heap [] # 存放较小的一半大根堆存负数 def addNum(self, num: int) - None: if not self.max_heap or num -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) if len(self.max_heap) len(self.min_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) elif len(self.max_heap) - len(self.min_heap) 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) def findMedian(self) - float: if len(self.max_heap) len(self.min_heap): return -self.max_heap[0] return (-self.max_heap[0] self.min_heap[0]) / 2.03.2 复杂度到底怎么算addNum的复杂度是O(log n)因为每次最多只向一个堆插入元素O(log n)可能再从一个堆里弹出并压入另一个堆又是O(log n)总体上还是O(log n)。findMedian的复杂度是O(1)。空间复杂度O(n)因为要存储所有数据。很多人觉得“两个堆每个堆操作一次那不就是2O(log n)吗”。大O记号忽略常数因子所以还是O(log n)但你面试时可以主动提一句“严格说常数因子是2”这显得你底子扎实。与数组方案对比一下同等数据量下50万次添加50万次查询双堆方案的总复杂度是 O(n log n)整体可控数组二分插入方案插入一次就是 O(n)最坏O(n²)直接超时。这就是双堆另一个层面上的优势——稳定。3.3 边界条件与常见坑点这题边界条件主要就几个我总结下来基本一次就能避开空堆时插入。addNum在第一次调用时maxHeap为空判断条件maxHeap.isEmpty()必须放在前面短路避免空指针。Java的PriorityQueue.peek()在空堆时返回null如果拿它做数值比较会NPE。负数处理。代码对负数天然无感因为比较大小只依赖堆序。但Python版本的大根堆用了取负数一定要注意-(-num)的正确还原。我在实际写的时候发现自己很容易在取负数的地方漏一个负号。数据范围溢出。两个堆顶相加可能超过int范围。题目约束是int范围但两个极端int相加确实会溢出。稳妥写法是(maxHeap.peek() minHeap.peek()) / 2.0之前先把其中一个转成double比如(maxHeap.peek() * 1.0 minHeap.peek()) / 2.0。虽然力扣测试用例一般不会真的卡这个点但做工程的人要有这个敏感度。重复元素。重复元素不影响正确性。判断条件用num maxHeap.peek()就是为了让重复元素稳定进入左堆减少左右搬运次数。你甚至可以把它当作“稳定性优化”。4. 扩展场景与实战经验4.1 数据流中位数真实业务里的身影说实话力扣题很多都是纸面功夫但数据流中位数这题绝对是面试题里少有的“它在业务里真的能被用到”的题目。最典型的场景是实时监控指标延迟、QPS、交易耗时分位数计算。比如网关服务要上报“p99响应时间”一次请求返回后数据不断进来你如果每次都把所有响应时间存下来排序算p99内存和CPU双重爆炸。用双堆结构维护一个大根堆和小根堆就能在常数时间内拿到准确的中间分位附近数据。要精确拿到任意分位数双堆虽然不够但它可以作为维护中位数的地基。另一个场景是滑动窗口中的数据统计。有些业务要求只统计最近5分钟的数据流中位数这时候每个元素还要记录时间戳从堆里惰性删除过期元素。你可以为每个堆额外配备一个延迟删除哈希表或者直接用带版本号的Pair进入堆。每次查询前先把过期堆顶元素踢干净再取堆顶。这个思想其实就是双堆的进阶玩法面试官继续追问时相当加分。还有个我实际做过的场景AB实验里实时看指标是否显著异常。对照组和实验组的指标流进来你要快速判断当前中位数是否偏移得厉害。以前的做法是每分钟拉全量数据重算数据量上去后作业跑得越来越慢后来换成双堆维护两组中位数几十行代码搞定还顺带解决了内存溢出的隐患。4.2 变体题与进阶思考力扣里凡是出现“数据流里找TopK”“找中位数”“找p%分位数”的题底层思路都是堆但各有侧重。数据流中的第K大元素标准做法是只维护一个大小为K的小根堆。堆顶就是答案。它和双堆的区别是中位数需要左右两半第K大只需要卡住阈值的那一半。滑动窗口中位数这题的解法是用双堆加上延迟删除。你在双堆基础上增加remove操作实现方式是通过懒惰删除用一个map记录待删除元素的频次每次poll之前先检查堆顶是否在延迟删除表里且在计数中是就弹出并更新计数直到堆顶是“真”元素。这个技巧在工程里非常实用我用它在一次实时数据分析任务里处理过上千万条数据。寻找两个有序数组的中位数力扣第4题这题看着一样但解法完全不同。它考的是二分法和归并思想而不是堆。很多面试者会把两题混淆一上来就双堆结果完全跑偏。这提醒了一个重要原则先看数据是不是静态的。静态数组用二分归并动态数据流用堆选型逻辑要清晰。数据流中的众数这类题直接哈希表就能搞定但如果你想同时维护中位数和众数需要双堆加哈希表的复合结构。按需组合不要迷信单一方案。4.3 流式计算里的分位数问题延伸一步聊流式计算。Flink、Spark Streaming这类框架里有一些内置的近似分位数函数比如Flink的QuantileDescriptor底层用的是GK算法或者TDigest。我第一次听说TDigest时想和双堆做个对比结论是双堆是精确且实现简单的方案但内存开销与全量数据规模线性相关TDigest是近似方案通过把数据聚成一个个桶来减少存储牺牲精度换内存在千亿级别数据流里更实用。我平时和人交流时喜欢说一个观点“双堆适合中小规模数据流如果数据量上亿、分位数要求多考虑TDigest或GK如果只是要中位数双堆永远是性价比之王。”这个判断到现在也没翻过车。5. 常见问题与排查技巧实录5.1 面试中常见的追问我面过不少候选人自己也被面试官用这道题拷打过总结一下高频追问“为什么用两个堆用一个堆行不行”单堆做不到。一个大根堆只能给你全局最大值或者最小值中位数不是这种极值。用一个大根堆存全部元素你只能拿到最大数无法定位中间位置。两个堆的本质是“把有序序列对半切让中间元素浮在两个堆顶附近”。“两个堆大小怎么维护你觉得最容易出错的是什么”最容易出错的是失衡判断反了。我见过很多同学写的代码是如果左堆比右堆多就搬左堆到右堆如果右堆比左堆多就搬右堆到左堆。听起来没错但边界条件一多就乱。我的建议是固定“左边必须大于等于右边且最多多1个”这个不变量所有调整都围绕它来做代码写起来就不容易飘。“数据流里有负数、重复值怎么办”负数完全不影响堆结构。重复值只要处理时候用的语义放进左堆就非常稳定。少数情况下极端重复全部进一个堆平衡规则会自动搬移到另一个堆没有问题。“添加和查询调用次数不相等比如查询时数据量很小怎么办”如果数据为空应该约定返回什么。一般面试里会说数据流非空才调用findMedian或者你主动处理空堆。我在代码里其实没处理空堆情况但解答时提一句“如果允许空数据流可以在findMedian里加个校验返回0或者抛异常”是最稳妥的。“如果数据一直增长内存爆了怎么办”内存必须存储全量数据这是题目限制面试官期待你主动说“这个方案的空间复杂度是O(n)无法优化到常数空间。如果数据量大到内存装不下就得上分布式或者近似算法。”能说出这一层基本就过关了。5.2 我自己踩过的坑第一个坑初始化时把大根堆和小根堆搞反。我早期在Java里写new PriorityQueue()默认是小根堆写大根堆要传一个reverseOrder()比较器。有次深夜写题大根堆定义忘了传参直接变成小根堆整个逻辑全反中位数算成了“最大数和最小数的平均值”排查了半天才找到原因。建议定义堆的时候加注释比如maxHeap注明是“左半段”minHeap是“右半段”。第二个坑平衡调整里的移动写错了方向。我见过自己写过的版本是“如果左堆比右堆多把左堆顶移到右堆”看起来对称但会导致左边越来越少、右边越来越多最终中位数永远取不到正确值。后来我改成只要比较完大小后严格按照规则搬运确保左堆数量在[右堆数量, 右堆数量1]区间内就不再出问题。这也是我在上文反复强调“固定不变量”的原因。第三个坑返回值类型错误。这个坑看起来很小实际非常阴间。Java里(maxHeap.peek() minHeap.peek()) / 2因为两个整数相加除以2结果是整数除法3.5就变成了3.0。如果你用类似方式实现很可能测试用例里普通数据全过一碰到奇数偶数组合就挂。改成/ 2.0或者先乘1.0再操作分分钟治好。第四个坑Python负数堆还原时漏符号。我写heapq.heappush(max_heap, -num)时从堆顶取值应该用-max_heap[0]但有时候复制粘贴时忘掉了那个负号导致取出的是负的中位数调试到怀疑人生。建议封装一层top_max()函数内部统一做取负减少心智负担。第五个坑在循环里频繁创建PriorityQueue对象。要是把MedianFinder的实例放在循环里反复创建每个实例都要堆初始化五万个对象带来的GC压力不是闹着玩的。实际使用中应该只保留一个单例或者用线程安全的替代方案加锁或用ConcurrentSkipListMap。5.3 实测下来的一种优化思路力扣官方题解里提到如果数据流中大部分整数落在给定区间内可以用桶计数来优化。我当时试过一版用一个int[] count数组统计区间内每个数的出现次数再用两个小堆维护区间外的极端值。插入时如果数字在区间内就count[num]在区间外就丢进对应的小堆。查询时先根据区间内计数和区间外元素数量确定中位数落在哪一侧再分情况计算。这个方案最复杂的点在于“确定中位数的落点”需要维护区间外元素的个数和区间两端的极值。我试过之后感觉如果数据分布真的比较集中这方案比双堆快代码也能写但调试难度高如果不确定数据分布双堆的通用性和可维护性明显更好。我的建议是把这个优化方案当作面试话题来聊但工程上默认先上双堆。不要过早优化这句话在算法题里同样适用。另外一个值得讲的细节是如果数据流非常稀疏或者数据有一个明显的偏移方向比如全是正数双堆工作时左右两堆的元素量可能长期不均衡。比如全是正数且一直递增num maxHeap.peek()这个判断总是为假新数据全部进右堆然后再搬一个到左堆执行效率还行但多了一次移动操作。更优雅的写法是同时比较左堆顶和右堆顶来决定插入方向if (maxHeap.isEmpty() || (minHeap.isEmpty() num maxHeap.peek()) || (!minHeap.isEmpty() num minHeap.peek())) { maxHeap.offer(num); } else { minHeap.offer(num); }这种写法按“中位数所在的夹缝区间”决策但条件稍显繁琐。我在实际写代码时还是保留了num maxHeap.peek()的简洁版本插入后靠平衡规则校正思路一致代码更好记。这里就看你的审美了没有绝对的优劣。6. 一些个人经验数据流中位数这道题值得反复刷。我第一次刷的时候只会抄官方题解代码过完几天全忘第二次刷才真正理解“大根堆放左半边、小根堆放右半边”这个朴素的切分思想第三次刷时已经能流畅地把这个思路迁移到滑动窗口中位数和流式分位数计算里。有时候刷题就是这样一个题当你从“会做”变成“能讲清楚为什么这么做”的时候它就不只是一道题了而是你脑海里的一套思考工具。双堆模型就是那种“一旦想通后面很多题都顺了”的模型。你现在如果正在被这题折磨把它当成一扇门跨过去后面就是一片开阔地。如果你准备把这题应用到真实项目中我唯一的建议是别一上来就整花活。先用最朴素的双堆方案跑通结合项目的压测数据看瓶颈在哪里再考虑是否引入延迟删除、桶优化或者TDigest这类进阶方案。算法题的“标准答案”和工程里的“最优解”从来都不是一回事双堆给了一个又好用又容易理解的起点这件事本身已经值回票价了。