流式运行众数:基于懒删除堆维护最高频值

某流式微观结构监控系统只想要一个滚动统计量:目前为止出现频率最高的整数编码值是哪一个? 成交流监控想要"最活跃股票",订单簿监控想要"最活跃价位",点击流监控想要"最热按钮"。这一数据结构必须随每次插入即时更新,任何一个值的重复次数都没有上限,并且要确定地处理平局——按惯例,平局时取最小的那个值。

实现 solution(values: list[int]) -> list[int]。每次插入后,把当前众数追加到输出列表。参考做法是用 dict 维护计数,再加一个语义上键为 (count, -value) 的大顶堆——具体落地为 Python 小顶堆,条目为 (-count, value),使得堆顶恰好是「最高计数 + 最小值」那一对。每次插入时把 counts[value] 加一并 push 新条目 (-new_count, value);不主动删除旧条目(heapq 没有高效的 decrease-key)。查询时执行懒删除:若 heap[0] 中记录的计数已不等于当前 counts[value],则将其 pop 并重新 peek。不变量是:真正众数对应的那条最新条目始终在堆中,所以循环必然终止于正确答案;均摊代价为每次插入 O(log N)。

举例:solution([3, 1, 3, 2, 2, 2]) 返回 [3, 1, 3, 3, 2, 2]。插入 3 后众数为 3。插入 1 后两者计数皆为 1,平局取较小者 1。再插一次 3,计数 {3: 2, 1: 1} → 众数 3。第一次插入 2 不改变领先者。第二次插入 2 时 2 与 3 在 count=2 处并列,取较小者 2。第三次插入 2 让 2 单独领先。

实践背景

流式众数是一族在线统计量中的基本砖块,与流式中位数(双堆)、流式 top-K(大小为 K 的堆)、流式分位数草图(quantile sketch)同源——它们的共同要点是:堆只是极值访问器,不是有序集合,所以当底层多重集合发生变更时,要么用平衡 BST,要么用计数小技巧,要么用懒删除。 当唯一操作是「插入」和「查询极值」时,懒删除就是首选答案:用一点常数开销换来不依赖 SortedList 或手写 BST。这个结构的现实形态包括 LeetCode 480(滑动中位数)、经典面试题「设计点击计数器/最活跃股票」,以及任何在交易日内监控行情、随时给出"最活跃 ticker"的服务。平局规则是候选人最容易翻车的地方——台桌之所以会把它写明,正是因为两种平局方向不同的实现,会在流动性差的日子给出两种完全不同的"赢家 ticker"告警。 </content> </invoke>