假设我们维护一个记录所有请求的网站。如何确定任意时间点最近 5 分钟内发出的请求数？
我可以在 5 分钟内找到解决方案。但不知道如何使它适用于任何时间间隔。
我的做法：
我们维护一个大小为 300 的数组。我们在数组中维护一个指针，该指针表示当前索引（每秒递增一次）。每当发出请求时，我们只返回指针所指的值。要首先填充数组，所有值都是累积的。例如，在第 1 秒发出的请求数为 3，在第 2 秒为 5，在第 3 秒为 0... 然后数组看起来像
3, 8, 8, 0...., 0 ，指针指向的位置索引 2 号。
（让我们快进到 4:59 分钟，数组的内容是） 3, 8, 8,....,180, 0
其中 ptr 指的是索引 298，因为我们没有填充第 299 个索引。
现在假设接下来 2 秒记录的请求数是 5 和 2。数组看起来像：
3、8、8、......、180、185（在 5:00 更新)
(185+2-3(oldvalue)), 8, 8, ...., 180, 185 => 184, 8, 8, .... .., 180, 185（5:01 更新）
ptr 指的是第 0 个索引。因此，截至目前，过去 5 分钟内发出的请求数为 184。
在类似的行中，我们应该能够在 O(1) 中的任何时间点返回值。
但是如何使解决方案通用？从某种意义上说，如果时间段是任意的，例如在过去 10 分钟、过去 20 分钟、过去 1 分钟内找不到请求，该怎么办。我认为我们可以利用段树，但我们最终会修改每一秒的所有值，这太昂贵了。提出一个 map reduce pgm 将是一个 O(N) 解决方案，以在发出对 getRequestsinLastNMins() 的请求时触发 pgm。但我正在寻找可以在 O(1) 中完成的事情。