algorithm - 滑动窗口上的最小值

Question

是否有特定的算法允许我在中小型滑动窗口(典型大小为 600，所有元素都是整数)上保持最小值/最大值？窗口实际上是流中的最后 N 个观察值。因此，我添加了一个新的观察结果并在每个时间单位删除了最旧的观察结果，因此我想保留最近 N 次观察的最小值和最大值。

这是一个与 Sliding window minimum algorithm 中所述的问题不同的问题。因为我不维护整个数据，因此“基于索引”的解决方案在这里不适用。此外，我的输入数据本身将在一个圆形数组中。

堆可能不会很好地工作:我不会删除/弹出 Min/Max 元素，而是删除/弹出最旧的元素，这将破坏首先拥有堆的目的。

log(n) 基于复杂性的结构(例如红黑树)可以正常工作，而张开树可能更适合我拥有的数据类型，但是对于我的大小来说，它们是否有点矫枉过正？ d 处理？

Answer 1

在输入数据流上找到最大值问题的解决方案托管在以下链接中，您可以轻松调整它以找到最小值。

输入流的大小并不重要，可以是无限的。该算法以摊销常数 O(1) 复杂度执行。

https://github.com/varoonverma/code-challenge.git