P4983.第3题-流式日志Top-K高频统计
题目内容
在大数据实时监控系统中，服务器每秒产生海量日志数据。为了快速识别热点事件、异常流量或热门关键词，需实现一个滑动窗口内的流式 Top-K高频词统计组件。该组件需要高效处理高频词的添加、过期和查询。
请实现一个支持以下两种操作的功能：
-
add(word)：向滑动窗口中添加一个关键词
1）窗口大小为 W，当窗口内元素超过 W 时，自动淘汰最早进入窗口的元素（FIFO 规则）。
2）被淘汰元素的频率计数需相应减少，若频率减为 0，则从统计中移除。
-
get_top(k)：返回当前窗口内频率最高的 k 个词
1）按频率降序排列，若频率相同，按字典序升序排列；
2）若有效词不足 k 个，返回所有有效词。
输入描述
1.第一行包含两个整数 W 和 Q，用空格分隔：
W：滑动窗口大小，数据类型为 int，范围 [1,100000]。
Q：操作总数，数据类型为 int，范围 [1,100000]。
2.接下来 Q 行，每行描述一个操作，格式为以下两种之一：
操作 1：add x，添加关键词操作
x：待添加的关键词，数据类型为字符串，由小写英文字母 [a−z] 组成，长度 [1,20]。
操作 2：get k，查询 Top−K 高频词操作
k：需要查询的高频词数量，数据类型为整型，范围 [1,100000]。
约束 1：输入数据保证，所有的 get k 操作在执行时，滑动窗口内至少有一个元素（即窗口不为空）。
约束 2：输入数据保证，每个测试用例中至少包含一次 get k操作（即每个输入都对应有输出）。
输出描述
对于每个 get k 操作，输出结果，若结果包含多个关键词，关键词之间用单个空格分隔，行尾无多余空格。
样例1
输入
5 10
add banana
add apple
add cherry
add banana
add apple
get 3
add durian
add apple
add pipeapple
get 5
输出
apple banana cherry
apple banana durian pipeapple
说明
1.操作 1−5：队列 [banana,apple,cherry,banana,apple] ，频率 banana:2, apple:2, cherry:1.
2.操作 6：频率相同，按字典序 apple<banana ，输出 apple banana cherry .
3.操作 7−9：队列滑动，最终频率
apple:2,banana:1,durian:1,pipeapple:1 .
4.操作 10：k=5 ，有 4 个词，按规则输出。
样例2
输入
3 8
add a
add b
add a
get 2
add b
add b
add b
get 2
输出
a b
b
说明
1. 操作 1−3: 队列 [a,b,a], 频率 a:2,b:1。
2. 操作 4: 按频率降序, 输出 ab。
3. 操作 5−7: 连续 add b, 队列变为 [b,b,b], 频率 b:3。
4. 操作 8: k=2, 只有一个词, 所以输出 b。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
