最小滑动窗口

发布时间：2020-12-14 02:16:36 所属栏目：Windows 来源：网络整理

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

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

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

堆可能效果不好：我不删除/弹出Min / Max元素,而是删除最旧的元素,这将首先破坏堆的目的.

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

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!