题干与适用场景
输入不是一次性数组，而是持续到达的整数流。结构需要 addNum(x) 与 findMedian()；不能每次排序全部数据。题目考察候选人是否能从“需要两侧顺序信息”推导双堆，而非只背答案。
面试官考察点
面试官关注两个堆的分工、大小平衡、顶部顺序不变量、偶数长度返回规则和重复值处理。强回答会先确认是否允许保存全部数据、数值范围、线程安全和近似结果；然后给出 O(log n) 插入、O(1) 查询和 O(n) 空间的证明。
回答前需要澄清的问题
- 数据流是否无界？允许保存所有元素，还是必须使用滑动窗口或近似摘要？
- 中位数定义是偶数个元素的平均值，还是下中位数/上中位数？
- 输入可能超出 64 位整数吗？平均值是否会溢出？
- 是否需要删除、撤销、按时间窗口查询或并发调用？
- 空流应抛出错误、返回空值，还是由调用方保证先插入？
30 秒回答框架
“我维护 max-heap low 保存较小的一半，min-heap high 保存较大的一半，并保持 low.top <= high.top、|low|-|high| 不超过 1。插入后先放入合适堆，再平衡大小；奇数长度返回较大堆或约定的中间值，偶数长度返回两个顶部的安全平均。每次插入 O(log n)，查询 O(1)，空间 O(n)。”
分步骤深入解答
第一步：固定中位数语义
常见定义是奇数长度取唯一中间值，偶数长度取两个中间值的平均。面试开始就写清楚，避免实现正确却与题目约定不同。若产品要求分位数或近似，可改用 t-digest 等摘要，但那是另一道题。
第二步：定义两个堆
low 是最大堆，存较小半部；high 是最小堆，存较大半部。所有 low 元素都不大于所有 high 元素，重复值允许出现在任意边界，只要不变量保持。
第三步：设计插入路径
若 low 为空或 x <= low.top，放进 low，否则放进 high。然后只移动一个顶部元素修复大小差。这样每次最多两次堆操作，不需要扫描全部数据。
第四步：保持大小平衡
让 low 的大小等于或比 high 多一。若 low 多两个，移动 low.top 到 high；若 high 多一个以上，移动 high.top 到 low。大小平衡保证顶部就是中位数候选。
第五步：处理查询与数值安全
空流返回明确错误。奇数长度返回较大堆顶部；偶数长度计算两个顶部的平均，先转为更宽类型或使用 a / 2 + b / 2 + (a % 2 + b % 2) / 2 等策略，避免整数相加溢出。
第六步：证明复杂度
插入会执行常数次堆 push/pop，每次 O(log n)；查询只访问一个或两个顶部，O(1)；两个堆合计保存 n 个元素，空间 O(n)。初始化堆的常数不改变渐进界。
第七步：说明替代方案
有序数组插入 O(n)，平衡树可做到 O(log n) 插入与 O(1) 或 O(log n) 查询，但实现复杂。计数直方图适合值域很小的整数；近似摘要适合无法保存全部流但允许误差的场景。
第八步：用边界测试验证
测试空流、一个元素、偶数长度、重复值、负数、单调递增/递减和极值。每次插入后断言堆大小差、顶部顺序和返回值；若实现线程安全，还要测试并发插入与查询的锁边界。
伪代码
add(x):
if low.empty() or x <= low.max(): low.push(x)
else: high.push(x)
if low.size() > high.size() + 1: high.push(low.pop())
if high.size() > low.size(): low.push(high.pop())
median():
if low.size() > high.size(): return low.max()
return safe_average(low.max(), high.min())设计取舍与边界
| 方案 | 插入 | 查询 | 适用边界 |
|---|---|---|---|
| 双堆 | O(log n) | O(1) | 精确、在线、保存全部数据 |
| 有序数组 | O(n) | O(1) | 数据量小、实现简单 |
| 平衡树 | O(log n) | O(1)/O(log n) | 还需要删除或排名 |
| 近似摘要 | 近似 | 近似 | 无界流且允许误差 |
双堆不支持高效删除任意旧值；滑动窗口需要延迟删除、索引或其他结构。它也不提供持久化、分布式一致性或跨机器合并，不能把单机算法直接当成流处理平台。
落地计划与证据
先实现双堆和边界测试，再加入溢出保护与指标。公开面试资料将该题描述为在线 order-statistics 设计，TechInterview 与 Intervu 都将 two-heaps 作为典型流式数据结构；若需要近似大规模分位数，再单独评估摘要算法。
试点的退出条件
所有边界测试通过；不变量在随机序列中始终成立；延迟和内存符合预算；极值输入不会溢出；API 对空流行为明确。
怎样证明收益不是巧合
与每次全量排序的基线比较插入吞吐、p95 延迟、峰值内存和结果一致性，并使用相同随机种子覆盖递增、递减、重复和极值分布。
常见误区与追问
每次插入都排序全部数据
这样插入是 O(n log n)，无法满足持续流的在线要求。双堆只维护边界信息。
两个堆大小相同就够了
还必须保持 low.top <= high.top。若直接分别插入而不按边界放置，顶部可能不是中位数。
忽略偶数长度定义
要明确平均、下中位数或上中位数，并处理平均时的类型转换与溢出。
如何支持滑动窗口？
为过期元素做延迟删除，用计数表标记并在堆顶清理；或者使用支持排名的平衡树。复杂度和内存边界需重新说明。
数据流无法全部保存怎么办？
如果允许误差，使用分位数摘要；如果要求精确中位数，就必须保存足够的顺序信息，不能声称常数空间完成一般问题。
多线程如何保证一致？
用读写锁或单线程事件循环保护两个堆与大小不变量；查询不能读到只更新一边的中间状态。