企业官网建设流程全解析

“数据流的中位数”这五个字，在准备面试的人眼里基本等同于“优先队列双堆”四个字。它被问到的频率高得吓人，但每次真到面试现场，能一次性写对的人并不多。这道题在力扣上的热度常年排在前列，因为它干脆利落地考察了一个关键能力：面对一个永远在变大的数据集合，你能不能设计出一种结构，让“插入”和“取中位数”都保持高效。这篇文章我直接给你搭好完整骨架，从题目拆解、双堆原理、代码模板，到我在提交和面试中踩过的坑，以及它背后的一整套扩展题型。适合正在刷力扣准备面试的朋友，也适合工作中要写实时统计逻辑的工程师，只要你会用优先队列，这篇吃透问题不大。

题干本身并不复杂：设计一个类，支持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。我习惯让左堆永远不小于右堆，也就是左堆要么比右堆多一个，要么两边相等。这样在元素总数为奇数时，中位数就是左堆堆顶；总数为偶数时，中位数才是两个堆顶的平均。

对应实现，业内最流行也最不容易出错的模板是三步走：

1. 新元素一律先塞进左堆。
2. 立刻把左堆的堆顶（也就是当前所有元素中的最大值）弹出来，塞进右堆。
3. 检查左堆大小是否小于右堆大小，如果是，就把右堆的堆顶弹回左堆。

第一步是无条件接收，第二步是把“过大的元素”分流到右堆，完成有序性修正，第三步是平衡性修正。这套流程最妙的地方在于，它不需要在插入前比较新数和堆顶的大小，避免了大量边界条件判断。你只管执行三步，堆会自动把大小顺序调好。我强烈建议你直接用这个模板，不要自己发明“先比较再插入”的写法，后者几乎每次都会漏掉一种边界情况。

2.3 手动模拟一次完整数据流

光讲理论不够，我拿一个真实序列走一遍：依次加入 5、2、8、4、7。约定左堆是最大堆，堆顶最大；右堆是最小堆，堆顶最小。

一步步看。先加 5，左堆一个元素，中位数是 5。加 2 时，如果只按先后顺序想，应该左边存 2、右边存 5，这样左堆最大值 2，右堆最小值 5，中位数 (2+5)/2=3.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默认是最大堆，所以左堆直接声明；右堆需要传greater<int>变成最小堆。

class MedianFinder { public: priority_queue<int> left; // 最大堆，存较小的一半 priority_queue<int, vector<int>, greater<int>> 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 { PriorityQueue<Integer> left; PriorityQueue<Integer> 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(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 再写一遍，每次都能发现语言特性对同一逻辑的不同表达方式。半年之后回来看，你会发现自己对堆和数据结构设计这件事的理解，已经完全不一样了。