题干与适用场景
你接手了一个 MedianFinder：较小的一半放最大堆，较大的一半放最小堆。它能处理 1, 2, 3，却会在 10, 1, 9, 2、大量重复值和极端整数下失败。本题要求调试现有实现，不再重复从零推导双堆。
面试官考察点
- 能否先写清不变量，再修改代码。
- 能否缩小失败序列，找到第一次非法状态。
- 能否覆盖空查询、重复值和偶数长度溢出。
- 证明、复杂度和实现是否一致。
回答前需要澄清的问题
- 第一次插入前调用
findMedian()应返回什么？ - 哪个堆允许多一个元素？
- 输入整数宽度和返回类型是什么？
- 是否允许重复值，并发是否在范围内？
本题假设重复值有效，下半堆可多一个元素，查询返回浮点数，空查询抛出明确错误；并发不在范围内。
30 秒回答框架
“我会在每次插入后检查两个不变量：下半堆和上半堆大小相等或下半堆多一个；两个堆都非空时，下半堆顶不能大于上半堆顶。先把失败输入缩成最小反例，再统一用‘插入下半堆—把最大值移到上半堆—必要时把上半堆最小值移回’修复。偶数长度先扩宽数值类型再求平均。最后用排序数组作真值，对短序列穷举并覆盖交替极值。”
分步骤深入解答
第一步：让错误状态可见
每次插入后记录输入前缀、两个堆的大小和堆顶，一旦不变量失效就停止。不断删掉输入值并重跑，直到得到仍能复现的最短序列。四个数的反例比一千个随机数更容易解释。
第二步：使用确定的插入流程
所有新值先进入下半堆，再把下半堆最大值移到上半堆；若上半堆变大，就把它的最小值移回。这个顺序先修复左右有序关系，再修复大小。只有最小堆的语言可在下半堆存负数，但符号转换要集中在边界。
第三步：处理查询与数值安全
两个堆都空时拒绝查询。总数为奇数时返回下半堆顶；总数为偶数时，先把两个端点转换为更宽或浮点类型再相加，避免固定宽度整数在中位数可表示时仍发生加法溢出。
第四步：证明并验证修复
把下半堆最大值移到上半堆后，留下的下半部不会越过边界；再移回一个上半堆最小值，只会恢复大小规则，不会破坏顺序。每次插入执行常数次堆操作，所以是 O(log n)；查询 O(1)，空间 O(n)。
每个前缀都与排序数组结果对照。测试空查询、一个值、两个极值、升序、降序、交替高低、全重复、负数，以及奇偶长度反复切换。
高质量示范回答
“我不会只修补当前失败分支。我先断言两个堆大小相等或下半堆多一个，并在两边非空时断言 max(lower) <= min(upper)。插入时统一先进入 lower，再把最大值移到 upper；只有 upper 更大时才把最小值移回。这样正确性不依赖输入顺序。
空结构查询会报错。奇数长度取 lower 堆顶，偶数长度先扩宽两个堆顶再求平均，避免极端整数溢出。我会让每个输入前缀都和排序数组真值比较，并对包含负数、零、重复值和极值的小集合穷举。复杂度仍是插入 O(log n)、查询 O(1)、空间 O(n)。”
常见错误
- 只平衡大小 → 两堆的值仍可能交叉 → 单独检查堆顶有序不变量。
- 只根据新值选择分支 → 旧堆状态可能继续非法 → 统一执行堆间移动。
- 用输入整数类型直接相加 → 极值平均会溢出 → 相加前扩宽。
- 只测有序且不重复的值 → 分支缺陷无法暴露 → 每个前缀对照并加入交替极值。
- 声称插入
O(1)→ 堆的 push/pop 是对数级 → 按真实操作计算复杂度。
追问及应对
如何找到最小失败输入？
逐个或分段删除输入并重跑不变量，保留仍然失败的最短前缀，再只分析导致第一次失效的那次插入。
为什么重复值不需要特殊分支？
不变量使用 <=，相等值可以落在任一侧。中位数由堆大小决定，与重复值的身份无关。
不信任另一份双堆实现时如何测试？
对小输入直接复制并排序，再按数学定义计算中位数。先穷举小字母表序列，再补固定宽度极值和大规模随机数据。
这套实现支持滑动窗口吗？
不支持。删除任意过期值需要可索引删除，或在两个堆上增加延迟删除计数；那是另一道独立题。