如果未对单词进行加权（权重0和1除外），则可以使用O（N）辅助存储来推导保持顺序的单词计数的简单数据结构，其中滑动中遇到N的 唯一
单词的数量窗口（在示例中为一小时）。可以及时执行所有操作（添加单词，使单词过期，查找最频繁的单词）O(1)。由于任何精确的解决方案都需要将所有唯一词保留在滑动窗口中，因此尽管每个词的常数因子不小，但该解决方案在渐近性上并不差。

解决方案的关键是任何给定单词的计数只能递增或递减1，并且所有计数都是整数。因此，可以维护一个双向 计数
列表（按顺序），其中列表中的每个节点都指向具有该计数的单词的双向链接列表。此外，单词列表中的每个节点都指向适当的计数节点。最后，我们维护一个哈希图，该哈希图使我们能够找到与给定单词相对应的节点。

最后，为了在其生命的最后腐烂的话，我们需要从滑动窗口，它的大小为保持整个数据流O(N')，其中N'在滑动窗口中遇到的单词总数。可以将其存储为单链接列表，其中每个节点都有一个时间戳和一个指向单词列表中唯一单词的指针。

当单词遇到或过期时，需要调整其数量。由于计数只能递增或递减1，因此调整始终在于将单词移至 相邻的
计数节点（可能存在或可能不存在）。由于计数节点存储在排序的链表中，因此可以及时找到或创建相邻节点O(1)。此外，始终可以通过从最大数量开始向后遍历计数列表来始终跟踪最流行的单词（和计数）。

如果不是很明显，这是给定时间点的数据结构的粗略ascii图：

Count list      word lists (each node points back to the count node)

  17            a <--> the <--> for
  ^
  |
  v
  12            Wilbur <--> drawing
  ^
  |
  v
  11            feature

现在，假设我们找到一个Wilbur。它将增加到13个。我们可以从以下事实的成功看12是不是13该13算节点需要创建和插入计数列表。之后，将Wilbur其从当前单词列表中删除，将其放入与新的count节点关联的新创建的空单词列表中，然后将count-
pointer更改Wilbur为指向新的count节点。

然后，假设使用drawing到期，那么它的新计数将为11。从这一事实可以看出，它的前身12是11不需要创建新的计数节点；因此，它的前身是。我们只需drawing从其单词列表中删除，然后将其附加到与关联的单词列表中11，就可以固定其计数指针。现在，我们注意到与关联的单词列表12为空，因此我们可以12从计数列表中删除计数节点并将其删除。

当单词的计数达到0时，我们将其0删除，而不是将其附加到不存在的count节点上。而且，如果遇到一个新单词，我们只需将该单词添加到1count节点，如果不存在则创建该count节点。

在最坏的情况下，每个单词都有唯一的计数，因此计数列表的大小不能大于唯一单词的数量。同样，单词列表的总大小恰好是唯一单词的数量，因为每个单词都恰好在一个单词列表中，而完全过期的单词根本不会出现在单词列表中。

- 编辑

这个算法有点耗费内存，但是拥有一个小时的推文确实没有任何麻烦。甚至一天的价值。几天后，即使考虑缩写和拼写错误， 唯一
单词的数量也不会发生太大变化。即使这样，还是值得考虑减少内存占用空间和/或使算法并行的方法。

为了减少内存占用，最简单的方法是仅删除几分钟后仍然唯一的单词。这将极大地减少独特单词的数量，而无需更改流行单词的数量。确实，您可以在不改变最终结果的情况下进行更多的修剪。

要并行运行该算法，可以通过使用哈希函数生成机器编号，将单个单词分配给不同的机器。（ 不
相同的哈希函数作为用于构造哈希表的一个。）然后顶端k的话可以通过合并顶部找到k从每个机器字; 通过散列进行分配可确保来自每台计算机的单词集是不同的。