Meta 滑动中位数：有序窗口基线到双堆延迟删除

题目重点：输出每个固定窗口的中位数，核对偶数窗口、重复值删除与实际数据结构复杂度。

题意与假设

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

窗口k正数，完整窗口才输出；奇数取中间值，偶数取中间两值平均。返回值允许浮点，输入不修改。
代码选有序列表作为可读基线；文章解释双堆升级，但不把基线插入删除声称O(log k)。

解题路线

首个窗口排序，滑动时二分找到离开值的一个出现位置删除，再有序插入新值。重复元素值相同，删除任意一个相同值即可。
Python列表二分O(log k)，但移动元素O(k)，所以此基线总体O(nk+k log k)。若约束很大，选平衡有序多重集合或双堆。
双堆保持lower有效元素数等于upper或多1，且max(lower)<=min(upper)。离开值计入delayed，弹堆顶时清理，rebalance用有效size而非heap实际长度。
延迟删除可能积累内部无效项；常见实现虽然每项只入出一次，但峰值堆空间可能O(n)，若要求严格O(k)需要重建或支持按ID删除的索引堆。

手动走一遍

[1,3,−1,−3,5]、k=3输出[1,−1,−1]；[1,1,2,2]、k=2输出[1,1.5,2]，重复值不能用set代替多重集合。

Python 参考实现

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

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

from bisect import bisect_left, insort


def sliding_medians(values, k):
    """Sorted-list baseline: Python list edits are O(k), not O(log k)."""
    if k <= 0:
        raise ValueError("positive window required")
    if k > len(values):
        return []
    window = sorted(values[:k])
    answer = []
    for left in range(len(values) - k + 1):
        answer.append(window[k // 2] if k % 2 else (window[k // 2 - 1] + window[k // 2]) / 2)
        if left + k < len(values):
            del window[bisect_left(window, values[left])]
            insort(window, values[left + k])
    return answer

复杂度

示例O(nk+k log k)时间、O(k)辅助空间；有序树升级O(n log k)、O(k)。双堆若只延迟清理则最坏空间可能O(n)，需给具体实现边界。

易错点与追问

容易失分的边界

把bisect时间等同整个insert/delete时间会低估列表成本。
双堆median查询前不清理无效堆顶，可能返回已离开窗口的值。

继续深挖

若值范围很小，可用频次数组/树状数组求第k/2个值，复杂度按值域而非窗口长。
要输出第p百分位，替换中位数顺序统计位置，说明离散百分位插值规则。