固定时间窗口内的流式中位数

某市场微观结构监控面板接收带标签的事件流 (ts, value)——比如当前买卖价差(单位:基点)、或往返延迟(单位:微秒)——每来一笔新事件都要打印 **过去 window_seconds 内的中位数**。滚动中位数比滚动均值在生产环境里要稳健得多:单笔异常打印(乌龙指、过期报价、路由抖动)不会把曲线拉飞,曲线干净地反映市场的「典型」状态,基于其上的告警逻辑也不会被尖刺反复触发。

实现 solution(events: list[list], window_seconds: int) -> list[float]。按时间顺序处理事件。每来一笔:先驱逐 所有活动集中 ts <= current_ts - window_seconds 的旧事件,再加入 新值,再计算 中位数。最终按输入顺序返回每笔事件对应的中位数。例如,solution([[1, 5.0], [3, 2.0], [8, 7.0], [12, 4.0], [20, 9.0]], 10) 返回 [5.0, 3.5, 5.0, 4.0, 9.0]。在 t=12 时 cutoff=2,t=1 处的 5.0 被驱逐;活动集变为 {2, 7, 4},中位数=4.0。在 t=20 时 cutoff=10,所有更早的事件都被驱逐,活动集只剩 {9},中位数=9.0。

参考算法是 双堆 + 惰性删除:大顶堆 lower 存较小一半,小顶堆 upper 存较大一半。用一个按 event id 索引的 FIFO 队列定位每步要驱逐的条目;把被驱逐的条目标记为墓碑,读堆顶前先剪掉墓碑。维护的尺寸不变量是 有效(未墓碑化)条目的 lower_size - upper_size ∈ {0, 1}。每次插入后还要恢复有序不变量 lower_max ≤ upper_min,必要时把两个堆顶交换。每个事件至多入堆一次、出堆一次,总开销 O(n log n)——和一次排序同阶,但是在线的、且支持窗口驱逐。

实践背景

时间窗口滚动中位数是 实时微观结构监控 里的看家原语:滚动中位数价差、滚动中位数报价延迟、滚动中位数订单簿失衡——只要某台桌想在异常打印不断的环境里追踪「典型」状态的漂移,就用它。双堆模式是 LeetCode 295(数据流中位数)的教科书解法;时间窗口滑动是把它推向生产化的关键变形,因为「每步重排再取中间」是 O(n) per step 跑不大,而二叉堆没有按值索引,真正的 del 要 O(n)。惰性删除——用墓碑标记并在堆顶处跳过——和实时推荐系统的滑窗 top-k、操作系统支持取消的优先队列、以及堆式定时器轮里用的是同一个技巧;均摊每个事件 O(log n),因为每个条目至多入堆一次、出堆一次。side[event_id] 表(记录条目当前在哪个堆里)是细节中容易漏掉、但承重的一处:漏了它,驱逐时会扣错某一侧的尺寸计数,中位数会悄悄偏一格。