追踪req数量的算法

Question

我有一个用于注册req的api，每个req都是在一个有数量的商店里出售。 ex。
销售：{时间戳：23212312312
金额：£500}

然后，我有一个函数统计负责给我在最后60秒内完成的销售细节。 统计将返回： 平均：平均都在最后60秒 分钟完成的销售金额的：分在最后60秒完成 最大的销售金额：最高金额
总和：所有的销售金额的总和在过去60秒内
计数：在过去60年代完成的销售数量

此功能在空间和时间上应该为O（1）。现在，如果我们忽略空间请求，是否应该使用链表来存储最近60秒内发生的销售并不断更新？或者当统计函数被调用时应该更新它。这怎么可能在O（1）空间中完成？

我的解决方案： 这是我解决这个问题的方法： 每次我们卖东西的时候，都会将该项添加到链表中。 由于java链表具有指向第一个和最后一个元素的指针，因此第一个元素将指向从现在开始60秒发生的第一个销售。当我们做销售时，我们从列表的开头删除元素，直到我们在60秒内完成。当我们调用统计信息时，我们将采用当前时间 - 60秒来查找时间戳，并使用它从列表的开头删除元素。但是当计算最小，最大平均值和总和时，我需要在空间和时间中遍历list => O（n）。

Answer 1

一种方法是将间隔分成1秒“桶”。 每个桶可以包含计数，总和，最小值和最大值。每次报告新的销售时，都要更新时间戳的相应存储桶。进行统计查询时，汇总存储桶以获取总计数，总和等。另外，对于每个API调用（更新或查询），丢弃60秒以前的存储桶并创建新的空存储桶以替换它们。

如果我们要作为一个参数k桶的数量，除了销售n的数量，然后更新单桶O(1)和查询统计是O(k)。在幼稚的实现中更新存储桶列表O(k)，但只有在访问存储桶时更新每个存储桶才能避免这种情况。空间要求是O(k)。

对于任何固定数量的存储桶，这会减少到每个操作的时间和空间复杂性，无论销售量如何。

您可以调整桶间隔以在精度和计算时间之间进行折衷。