从不断更新的列表中获取最大数量

Question

几天前我在系统设计面试中遇到了这个问题。我将省略无关的部分，以专注于问题的核心部分。事情是这样的。

假设我们有一组 k,v 对，键是字符串，值是整数。我们可以假设有一组固定的键（例如k1，k2，...，kn）。有一些代理将这些 k,v 对连续推送到系统中，就像流一样。我们需要做的就是将所有传入对的当前值添加到旧值。

让我们举个例子。在时间t0，我们假设我们有以下 kv 对。

k1: 100
k3: 200

此时t1，有两对传入。k2: 50, k3: 150. 因此，在 时t1，系统的状态为：

k1: 100
k2: 50
k3: 350

目标是给出在周期性间隔内具有最大值的密钥。我想不出任何算法可以比 max-heapify 提供更好的运行时间。我想到构建一个最大堆，然后在每个新数据出现时更新它。对于每次更新，heapify()将花费最log(n)长时间。在每次调用时，我们都可以返回堆的根。但还有比这更好的解决方案吗？

Answer 1

将最大值和关联的键保留在内存中。每次处理传入的键值对时，请将已处理键的新值与最大值进行比较，并更新是否有新的最大值。