我们有一个格式为 - {val, timestamp} 的输入流。时间戳严格增加。值是整数(32 位)。我们只对最后 n 个时间戳事件感兴趣。例如。如果 n 为 100 并且调用 add(400, 12)，我们只对时间序列 [300, 400] 感兴趣。我们还希望能够搜索最近 n 个时间戳事件。
对于搜索，如果没有具有特定时间戳的值，我们希望返回前一个时间戳的值(假设前一个时间戳在 [latestTimestamp-n，latestTimestamp] 范围内)。
解决这个问题的一种方法是使用二叉搜索树(C++中的map)。添加时，我们会将元素添加到 BST 中。因此，add 的复杂度为 O(log n)。对于搜索，我们只需进行 lower_bound(在 C++ 中)搜索并检查时间戳是否落在有效范围内([latestTimestamp-n，latestTimestamp])。搜索的复杂度也为 O(log n)。
我想知道是否有一种算法具有更好的时间复杂度，即使以增加空间复杂度为代价？我对提高搜索(时间戳)操作的时间复杂度更感兴趣。
最佳答案
由于您添加的每个时间戳都位于前面的所有时间戳之后，而您删除的时间戳始终是最前面的，因此您只需要一个支持快速搜索的队列即可。
如果您使用动态数组支持的队列(如 Java 中的 ArrayDeque)，则可以在摊销常数时间内完成在末尾添加一个新条目，并从开头删除任何过时的条目。搜索将是一个简单的二分搜索，并且需要 O(log N)。
关于algorithm - 搜索是按时间线顺序排列的吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53890132/