可能重複：
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