可能重复：
Find the min number in all contiguous subarrays of size l of a array of size n计算移动最大
我有数字数据的（大）阵列（大小N），并想以计算与运行最大值的阵列一个固定的窗口大小w。
更直接地，我可以为k >= w-1定义一个新的数组out[k-w+1] = max{data[k-w+1,...,k]}（这里假定为0的数组，如C++所示）。
有没有更好的方法来做到这一点比N log(w)？
[我希望在N应该有一个线性的，不依赖于w，就像移动平均值一样，但是找不到它。对于N log(w)我认为有一种方法来管理一个排序的数据结构，这将执行insert()，delete()和extract_max()总共在log(w)或更少的结构的大小w - 例如像排序的二进制树]。
非常感谢。
确实有一种算法可以在O（N）时间内完成，而不依赖于窗口大小w。我们的想法是使用支持下列操作一个聪明的数据结构：
这实质上是一个队列数据结构，它支持最大元素的访问（但不能移除）。令人惊讶的是，如this earlier question所示，有可能实现这种数据结构，使得这些操作中的每一个以分期O（1）时间运行。因此，如果你使用这个结构排队w元素，那么在需要时调用find-max不断出列并排队另一个元素，它将只需要O（n + Q）时间，其中Q是查询你所做的。如果你只关心每个窗口的最小值，那么这个值就是O（n），而不依赖于窗口大小。
希望这会有所帮助！
我将演示如何使用列表中做到这一点：
L = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]
长度为N=23和W = 4。
让你列表的两个新副本：
L1 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]
L2 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]
环路从i=0到N-1。如果i不能被W整除，则用max(L1[i],L1[i-1])替换L1[i]。
L1 = [21, 21, 21, 21, | 3, 9, 11, 18, | 19, 19, 19, 23 | 20, 20, 20, 20 | 1, 2, 22, 22 | 8, 12, 12]
环路从i=N-2到0。如果i+1不能被W整除，则将L2[i]替换为max(L2[i], L2[i+1])。
L2 = [21, 17, 16, 7 | 18, 18, 18, 18 | 23, 23, 23, 23 | 20, 15, 14, 14 | 22, 22, 22, 13 | 12, 12, 6]
制作长度N + 1 - W列表L3，使L3[i] = max(L2[i]，L1[i + W - 1])
L3 = [21, 17, 16, 11 | 18, 19, 19, 19 | 23, 23, 23, 23 | 20, 15, 14, 22 | 22, 22, 22, 13]
然后这个名单L3是你所寻求的移动最大值，L2[i]是i和未来之间的最大范围垂直线，而l1[i + W - 1]是垂直线和i + W - 1之间的最大范围。
这么好，我不得不赞同这个答案和你引用的答案！ – Andy 2012-01-18 05:31:12
我必须在这里评论说，双栈队列实现不一定是最好的。我试过了，对于一个实时应用程序，结果是灾难性的......根据应用程序，人们也可以尝试deque（双端队列）结构，它也会给出O（N）结果，但不一定为O（1）摊销操作。我在数组上实现了一个循环deque，它运行良好。看看这个问题以及：https://stackoverflow.com/questions/12329073/find-the-min-number-in-all-contiguous-subarrays-of-size-l-of-a-array-of-size -n。 – Alan 2017-09-18 00:41:05