如何在恒定时间内获得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).