Amazon Coding：滑窗中位数，离窗删除和双堆大小怎样保持正确？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 题目明确滑动窗口中位数，但未给题号、输入上限、偶数定义或复杂度要求；本文标准固定窗口训练，原合同仍待核。
• 整数序列、1≤k≤n，输出每个连续k窗口中位数，偶数取两中值算术平均；Fraction保证大整数/半整数精确，未宣称接口与原判题一致。
• 示例是有序列表基线，不声称bisect让Python list移动变成O(log k)。

解题路线

1. 维护窗口的有序多重集。首窗排序，取rank k//2；偶数另取k//2−1。每次删除一个离窗值，再插入一个新值，重复数删除一个即可，不能把同值全删。
2. 代码bisect_left定位离窗值、pop删除、insort插入。定位O(log k)，数组元素移动O(k)；中位数读取常量阶，空间O(k)不含输出。基线适合先核正确性，面试要求O(n log k)时继续讨论改进。
3. 双堆让low为下半最大堆、high为上半最小堆，保持low逻辑大小等于high或多1，且low有效最大值≤high有效最小值。奇数取low顶，偶数取两顶。逻辑size不等于含失效元素的数组长度。
4. 出窗使用delayed[value]计数标记，离窗元素属于low/high的判断必须先清理堆顶，并按当前分割边界调整逻辑size；跨边界的同值可视作可交换副本，但计数只能消费一次。balance前后清顶，再移动有效元素。
5. 常见惰性堆实现有远离堆顶的旧值长期不弹，物理堆可长到O(n)，不能一概标O(k)内存或O(log k)操作。严格O(k)可用indexed heaps按唯一index删除，平衡树/order-statistic，或定期从当前窗口重建并分析摊还成本。
6. 验证以窗口内逐值排名关系为独立参考，不维护同样的有序滑窗；重点包括全重复、递增/递减、k=1、k=n、负数和超大整数。bisect性能依据：https://docs.python.org/3/library/bisect.html。

手动走一遍

[1,3,−1,−3,5,3,6,7]，k=3，中位数[1,−1,−1,3,5,6]。k=2的[10^100,10^100+1]精确中位为10^100+1/2，不先转float。某个负小数离开low却不在顶，逻辑size先减少，不能等待它将来弹出时再减一次。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from bisect import bisect_left, insort

def sliding_medians(values, k):
    """Training contract: integer input, exact integer/half-integer outputs."""
    if type(k) is not int or not 1 <= k <= len(values):
        raise ValueError('k outside window range')
    if any(type(x) is not int for x in values):
        raise TypeError('integer input required')
    window = sorted(values[:k])
    result = []
    for end in range(k, len(values) + 1):
        if k % 2:
            result.append(window[k // 2])
        else:
            # Fraction avoids rounding large integers through float.
            from fractions import Fraction
            result.append(Fraction(window[k // 2 - 1] + window[k // 2], 2))
        if end < len(values):
            window.pop(bisect_left(window, values[end-k]))
            insort(window, values[end])
    return result

复杂度

附代码O(k log k+(n−k)k)时间，O(k)工作空间、O(n−k+1)输出；整数运算与Fraction另受位宽影响。indexed heaps/平衡多重集可做到O(n log k)、O(k)状态，朴素惰性堆不自动具备这些界。

易错点与追问

容易失分的边界

• 出窗重复数全部删除。
• 按物理heap长度balance。
• 重复减少失效元素size。
• insort二分就报log复杂度。
• 超大整数先float。

继续深挖

• 双堆如何按唯一索引删除？
• 惰性删除内存为何能增长到n？
• 在线流如何保留离窗索引？
• 偶数中位必须精确有理数吗？