最小滑动窗口

Question

是否有特定的算法允许我在小/中型滑动窗口上保持最小/最大(典型大小为600,所有元素都是整数)？窗口实际上是流中的最后N个观察值.所以,我添加了一个新观察并删除了每个时间单位的最老观察,所以我想保持最后和最大值超过最后N个观察点.

这与滑动窗口最小算法中所述的问题不同,因为我不维护整个数据,因此"基于索引"的解决方案在此不适用.此外,我的输入数据本身将是一个圆形数组.

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

log(n)基于复杂性的结构(如红黑树)可以很好地工作,而splay树可能更适合我所拥有的数据类型,但它们对于我的大小来说有点过分. d处理？

Answer 1

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

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