题目重点：题目只说流数据 Top K 与候选人提出 bucket O(1) 优化；本文先拆最高值、最高频、窗口三种口径，再给可检查的成本与适用边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练基线选择无限流中按数值大小维护当前最大的 K 个元素，重复值按出现次数保留；这是一个可能解释，不宣称题目固定此口径。
- 若题意改为频率最高的 K 个不同元素或最近 W 时间窗，数据结构与过期规则必须重建。
- K≥1，结果可无序返回；若要每次查询有序结果，还需 O(K log K) 排序。
解题路线
- 先问‘Top’按值、频次、得分还是最近时间，允许多少内存、每条更新后要不要立刻查询、元素是否会过期。用一两个反例让面试官确认。
- 按数值取前 K 的通用方案是大小 K 的最小堆：未满就插入，满后只有新值大于堆顶才替换；每条 O(log K)，空间 O(K)，不需保存全部流。
- bucket 若元素或分数来自小而固定的离散值域，可按值维护计数桶，更新 O(1)，但取前 K 需要扫描桶或用最高非空位置索引；若值域巨大/连续，直接建桶会浪费空间。若是频次 Top K，哈希计数加堆/桶的更新与失效又是不同问题。
手动走一遍
训练例 K=2，流 [4,1,7,3]：最小堆依次保留 [4]、[1,4]、[4,7]、[4,7]。若数值只有 0..9，可用十个桶计数并从高到低读出 7、4；但 64 位任意整数值域不能直接建 2^64 个桶。
规模与取舍
通用数值 Top K 的每项处理 O(log K)、空间 O(K)。值域大小 U 有界的计数桶更新 O(1)、空间 O(U)，查询朴素 O(U+K)；若要求滑窗过期，还要按时间/队列删除旧贡献。题目的‘bucket O(1)’不能脱离操作类型和 U 宣称全流程 O(1)。
易错点与追问
容易失分的边界
- 未问排名口径就直接写最大值堆。
- 声称 bucket 使查询和更新都 O(1)，却需扫描巨大值域。
- 无限流保存全部元素再排序，违反流式内存目标。
- 窗口题不处理旧元素过期。
- 把候选人现场提出的复杂度当成已被证明的原题要求。
继续深挖
- 如果要每条更新后立刻输出有序 Top K，成本怎么变？
- 若按频次而非数值排名，如何处理同频与热点 key？
- 最近一小时窗口内 Top K 遇乱序时间戳怎样清理？
