performance - 如何在恒定时间内获得N个计数器中的最大值？

Question

我们有 N 个整数计数器，最初显示为 0。操作:

int getMax() - 返回计数器显示的最高值。
void increment(int i) - 增加计数器 i 的值。
void zero() - 为所有计数器设置零值。备选名称是 flood()，也许这个名称会对您有所帮助。

这些操作和底层数据结构的当前实现，知道我们希望这些操作尽可能快。

---

这是我的面试问题。由于我的内存力不足，有很小的机会我说错了，但我尽力了。也许它类似于一些众所周知的问题？ (我希望。)

据我所知，所有操作都可以在 O(1) 内完成...其中一个操作是“惰性”操作(可能是 increment)...即在调用的那一刻它什么都不做，但后来当用户使用 getMax() 请求值时 - 它起作用了。

Answer 1

这可以简单地用一个大小为 N 的数组来完成，其中每个元素由 2 个数字组成 - 当前值和一个版本(例如时间戳)。并且您还需要一个全局最后重置(归零)版本和一个全局最大值。

递增:

• 如果该元素的版本低于全局版本，只需将其值设置为 1。否则增加它。
• 如果它大于全局最大值，则将全局最大值设置为其值。
• 适本地设置它的版本(到当前时间)。

获取最大值:

• 简单地返回全局最大值。

重置:

• 简单地设置全局最后重置版本(到当前时间)并将全局最大值设置为 0。

所有操作:O(1)。