LeetCode 面试题 17.20. 连续中值
目录
题目描述
题意分析
题目要求设计一个数据结构，支持两种操作：
addNum把一个整数加入数据流，findMedian返回当前所有已加入元素的中位数。数据是持续到来的，不是一次性给定的数组，所以不存在「先拿到全部数据再处理」的机会，每一次查询面对的都是一个随时可能变长的集合。中位数的定义要看清楚：把已加入的元素排好序后，如果个数为奇数，中位数是正中间那个数；如果个数为偶数，中位数是中间两个数的平均值。平均值意味着返回类型必须是浮点数，而不是整数。
约束里有两个明显的信号。第一，
addNum和findMedian的调用次数最多可以到 $5 \times 10^4$ 量级，两个操作交替出现，所以单次操作的代价必须足够低，不能让某一个操作退化成线性甚至更差。第二，元素值域是 $[-10^5, 10^5]$，是一个有限且不大的范围，这是一个留给进阶优化的伏笔。边界情况：数据流为空时不会调用
findMedian，所以不必处理空集合；只有一个元素时中位数就是它自己；元素可以重复，也可以是负数，中位数本身不要求是数据流中出现过的数。
解法：双堆维护中位数
核心思路
最朴素的写法是把所有数字塞进一个动态数组，每次查询中位数时排一遍序再取中间。这样
addNum是 $O(1)$，但findMedian是 $O(n \log n)$，交替调用时总代价直奔 $O(n^2 \log n)$，在 $5 \times 10^4$ 次操作下无法接受。稍作改进，改成插入时用二分找位置、保持数组始终有序，查询就变成 $O(1)$，可代价转移到了插入：找位置只要 $O(\log n)$，但为了腾出空位仍然要搬移后面的所有元素，插入依旧是 $O(n)$。瓶颈在于我们维护了「完整的有序性」，而中位数根本不需要这么多信息。观察一下：要回答中位数，只需要知道排序后正中间那一两个数是谁，两侧的元素究竟按什么顺序排列完全无关紧要。换句话说，我们只需要把集合切成「较小的一半」和「较大的一半」，并且能随时问出较小一半里的最大值、较大一半里的最小值——而「求一堆数里的极值并支持动态增删」正是堆最擅长的事。
于是用两个堆：大顶堆
small存较小的一半，小顶堆large存较大的一半。整个解法建立在两条不变量之上，任何一次操作结束时它们都必须成立：其一是有序划分不变量：
small中的每个元素都不大于large中的每个元素。等价的可检验形式是small的堆顶（较小一半的最大值）不大于large的堆顶（较大一半的最小值）。这条保证了两个堆顶恰好夹在整个有序序列的中间位置。其二是大小平衡不变量：两堆的元素个数之差不超过 1，且约定多出来的那一个永远归
small。也就是small.size()等于large.size()，或者比它多 1。这条保证了元素总数为奇数时中位数就是small的堆顶，为偶数时是两个堆顶的平均值。难点在于插入时如何同时维持这两条不变量。新数字来的时候，我们并不知道它该去哪一半——它可能比
large的堆顶还大，也可能比small的堆顶还小。逐个比较判断当然可行，但分支会变多且容易漏情况。更干净的技巧是「先入对面堆，再把堆顶转移过来」：想让元素最终落在small一侧的容量增长时，先把它放进small，再从small弹出堆顶塞给large，最后如果large变得比small多，就把large的堆顶弹回small。这个套路为什么能自动维持有序划分？关键在于「弹堆顶」这个动作本身就是在做筛选。把新数 $x$ 压进
small后，small的堆顶必然是新的最大值，它要么是 $x$ 自己（说明 $x$ 属于较大一半，应该被送走），要么是原来的最大值（说明 $x$ 比它小，理应留在较小一半，而被送走的那个原最大值本来就是较小一半里最该晋升的候选）。无论哪种情况，被移交给large的都恰好是「合并后应该属于较大一半的那一个」，我们不需要写任何显式的比较分支。反向把large堆顶弹回small时同理，弹出的是较大一半的最小值，也正是最该降级的元素。两次转移都只经手极值，划分自然不会被破坏。至于实现细节：Java 的
PriorityQueue默认是小顶堆，这里用存相反数的方式模拟大顶堆，省掉自定义比较器；由于取反可能触及边界，统一用long存储更稳妥。Go 代码手写了上浮pushHeap和下沉popHeap，同样把small存成相反数，逻辑与 Java 完全等价。
解题步骤
- 准备两个堆：大顶堆
small装较小的一半，小顶堆large装较大的一半。之所以要一大一小两种堆顶方向，是因为我们只关心分界处的两个数，small要能吐出它的最大值，large要能吐出它的最小值。addNum第一步：把新数字压入small。这一步不做任何比较，因为接下来的转移会自动纠正位置。addNum第二步：弹出small的堆顶，压入large。弹出的一定是当前较小一半里的最大值，它是最有资格「晋升」到较大一半的元素，所以转移之后有序划分不变量依然成立。addNum第三步：如果此时large的元素个数超过了small，就弹出large的堆顶压回small。弹回的是较大一半的最小值，是最该「降级」的元素，划分同样不受影响。这一步把多出来的那个元素固定归给small，兑现了大小平衡不变量的约定。findMedian：若两堆等大，说明元素总数为偶数，返回两个堆顶的平均值，注意用浮点除法；若不等大，只可能是small多一个，说明总数为奇数，直接返回small的堆顶。- 以
addNum(1)、addNum(2)、findMedian、addNum(3)、findMedian走一遍：初始两堆皆空。addNum(1)：1 先入small，再弹给large，此时large有 1 个元素而small有 0 个，触发回弹，结果small = [1]、large = []。addNum(2)：2 入small得到[2, 1]，弹出堆顶 2 给large，此时small = [1]、large = [2]，两堆等大不再回弹。findMedian：两堆等大，返回 $(1 + 2) / 2 = 1.5$。addNum(3)：3 入small得到[3, 1]，弹出堆顶 3 给large得到large = [2, 3]、small = [1]，此时large比small多，回弹large的堆顶 2，最终small = [2, 1]、large = [3]。注意 3 虽然是从small出发的，却精准地留在了较大一半，而被换回来的 2 也正确地归入较小一半。findMedian：small比large多一个，返回small的堆顶 2。两次查询结果为 1.5 和 2，与直接排序[1, 2]和[1, 2, 3]的中位数一致。
代码实现
class MedianFinder {
private PriorityQueue<Long> small;
private PriorityQueue<Long> large;
public MedianFinder() {
small = new PriorityQueue<>();
large = new PriorityQueue<>();
}
public void addNum(int num) {
// small 用相反数模拟最大堆，堆顶对应较小一半的最大值。
small.offer(-(long) num);
large.offer(-small.poll());
if (large.size() > small.size()) {
small.offer(-large.poll());
}
}
public double findMedian() {
if (small.size() == large.size()) {
return ((-small.peek()) + large.peek()) / 2.0;
}
return -small.peek();
}
}
type MedianFinder struct {
small []int
large []int
}
func Constructor() MedianFinder {
return MedianFinder{}
}
func (this *MedianFinder) AddNum(num int) {
// small 保存较小一半的相反数，因此它按最小堆维护。
this.small = pushHeap(this.small, -num)
moved := -this.small[0]
this.small = popHeap(this.small)
this.large = pushHeap(this.large, moved)
if len(this.large) > len(this.small) {
moved = -this.large[0]
this.large = popHeap(this.large)
this.small = pushHeap(this.small, moved)
}
}
func (this *MedianFinder) FindMedian() float64 {
if len(this.small) == len(this.large) {
return float64(-this.small[0]+this.large[0]) / 2.0
}
return float64(-this.small[0])
}
func pushHeap(heap []int, value int) []int {
heap = append(heap, value)
for child := len(heap) - 1; child > 0; {
parent := (child - 1) / 2
if heap[parent] <= heap[child] {
break
}
heap[parent], heap[child] = heap[child], heap[parent]
child = parent
}
return heap
}
func popHeap(heap []int) []int {
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for parent := 0; ; {
left := parent*2 + 1
if left >= len(heap) {
break
}
child := left
right := left + 1
if right < len(heap) && heap[right] < heap[left] {
child = right
}
if heap[parent] <= heap[child] {
break
}
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
}
return heap
}
复杂度分析
- 时间复杂度：
addNum为 $O(\log n)$，因为它固定执行常数次堆的插入与弹出，每次操作的代价是堆高度 $O(\log n)$；findMedian为 $O(1)$，只读取两个堆顶，不做任何调整。$n$ 次插入的总代价为 $O(n \log n)$。- 空间复杂度：$O(n)$，两个堆合起来保存了数据流中的全部元素，除此之外只用了常数个临时变量。
关键点总结
- 「只要中间值就别维护全序」是一条可迁移的降本原则。完整排序提供的信息远超需求，把集合按需切成若干块、每块只暴露极值，往往能把 $O(n \log n)$ 的查询压到 $O(1)$。
- 「先入对面堆再转移堆顶」是双堆题的通用模板。它用两次极值操作替代了显式的大小判断分支，代码更短、也更不容易漏掉「新元素恰好落在分界线上」这类边界。
- 不变量要写成可以随时检验的形式。「
small堆顶 ≤large堆顶」和「small.size()减large.size()属于 ${0, 1}$」这两句话，是调试时逐步打印就能验证的断言，比「大概保持平衡」这种模糊描述有用得多。- 多出来的元素归哪一边必须提前约定死。约定归
small之后，奇数情况的取值代码只有一行；如果不约定，findMedian就要分三种情况讨论。- 面试视角：这题几乎必然会追问「如果所有数字都在 0 到 100 的范围内，怎么优化」。答案是改用计数数组，开一个长度 101 的桶记录每个值出现的次数，
addNum变成 $O(1)$ 的自增，findMedian则从头累加前缀计数，找到第 $\lfloor (n+1)/2 \rfloor$ 和第 $\lceil (n+1)/2 \rceil$ 个元素落在哪个桶，代价是 $O(100)$ 即常数。若追问再变成「99% 的数字都在 0 到 100 范围内，剩下 1% 是任意值」，则用「桶 + 两侧溢出堆」的混合结构：范围内的走计数数组，范围外的分别丢进一个大顶堆和一个小顶堆，查询时先看两侧溢出的数量再决定从哪里数起。- 面试视角：还常被问「能不能保证
findMedian严格 $O(1)$ 且addNum也 $O(1)$」。在比较模型下这是做不到的，因为那等价于 $O(n)$ 完成排序；这时应当直接指出下界，而不是硬凑方案。
易错点总结
- 错误写法：直接把新元素放进当前 size 较小的那个堆，不做交叉转移。用例
addNum(5)、addNum(1)、addNum(2)→ 5 进small，1 因为large更小而直接进large，此时small的堆顶 5 大于large的堆顶 1，有序划分已经被破坏；再插入 2 后findMedian会返回 $(5 + 1) / 2 = 3$，而正确答案是 2。大小平衡看似满足，划分却错了，这类 bug 在小样例上未必暴露。- 错误写法：只做「入
small、弹给large」两步，省掉第三步的回弹。用例addNum(1)→small为空、large = [1]，随后findMedian读取small的堆顶直接崩溃；即便不崩溃，large也会永远比small多，奇数情况的取值全部取错一位。- 错误写法：把回弹条件写成
large.size() >= small.size()。用例addNum(1)、addNum(2)→ 本该形成small = [1]、large = [2]的均衡状态，却被强行把 2 弹回small，large变空，findMedian返回 2 而不是 1.5。回弹只应在large严格多于small时触发。- 错误写法：偶数情况用整数除法求平均，写成
(small.peek() + large.peek()) / 2。用例addNum(1)、addNum(2)→ 期望 1.5，实际得到 1。必须除以2.0，或先转成浮点再相加。- 错误写法：Java 用
int存相反数并在极端值上取反。用例中若出现Integer.MIN_VALUE，-num会溢出回自身，导致堆序完全错乱。用long保存或先转宽再取负是安全做法。- 错误写法：
findMedian用small.size() > large.size()之外的条件判断奇偶，比如自己额外维护一个count计数器却忘记在回弹分支同步更新。用例是任意一串插入 → 计数与实际堆大小脱节，奇偶判断错位。直接读堆的 size 就不会有这个问题。- 错误写法：把
small定义成小顶堆、large定义成大顶堆（方向搞反）。用例addNum(1)、addNum(2)→small的堆顶给出的是较小一半的最小值，根本不是分界元素，中位数无从谈起。记住口诀：两个堆顶要「相对而立」，都朝着分界线的方向。- 错误写法：Go 手写堆的
popHeap里先截断切片再取堆顶，或者下沉时用旧长度做边界判断。用例是任意超过两个元素的插入序列 → 越界 panic 或者堆序被破坏。正确顺序是先取出堆顶值、把末尾元素搬到根、再截断，然后按新长度下沉。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 480. 滑动窗口中位数 | 困难 | 双堆还要支持窗口滑出时的删除，需配合延迟删除或有序集合 |
| 剑指 Offer 41. 数据流中的中位数 | 困难 | 同款双堆模板，可作为默写复现的对照题 |
| 703. 数据流中的第 K 大元素 | 简单 | 只需单个容量为 K 的小顶堆，不涉及两堆之间的平衡 |
| 215. 数组中的第K个最大元素 | 中等 | 静态数组求第 K 大，可用快速选择做到平均 $O(n)$ |