题目内容

在大数据实时监控系统中，服务器每秒产生海量日志数据。为了快速识别热点事件、异常流量或热门关键词，需实现一个滑动窗口内的流式 Top-K高频词统计组件。该组件需要高效处理高频词的添加、过期和查询。

请实现一个支持以下两种操作的功能：

1. $add(word)$：向滑动窗口中添加一个关键词

   1）窗口大小为 $W$，当窗口内元素超过 $W$ 时，自动淘汰最早进入窗口的元素（$FIFO$ 规则）。

   2）被淘汰元素的频率计数需相应减少，若频率减为 $0$，则从统计中移除。

2. $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$: 按频率降序, 输出 $a \; b$。

$3$. 操作 $5-7$: 连续 $add$ $b$, 队列变为 $[b, b, b]$, 频率 $b: 3$。

$4$. 操作 $8$: $k=2$, 只有一个词, 所以输出 $b$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写