滑動視窗最大值問題

前言：滑動視窗最大值問題是很經典的演演算法問題。本文描述了它的求解過程，分析了時間複雜度，證明了其正確性。

用一個長度固定的滑動視窗W在一個陣列上逐元素滑動，求每次滑動後W內的最大元素。例如：長度為3的滑動視窗在陣列[3,4,1,5,2]上滑動，在(a)和(b)兩個時刻視窗內最大值分別為4和5。如下圖所示：

你可以在leetcode上找到相關題目。

最容易想到的方法就是遍歷每一時刻下滑動視窗內的所有元素，找到其最大值。整個過程簡單直觀，無需證明。複雜度上，易得空間複雜度是O(1)，時間複雜度是O(N*K)，其中N是陣列長度，K是滑動視窗大小。因為需要滑動N次，每次遍歷K個元素。

高階解法在整個滑動過程中維護了一個佇列Q。某時刻滑窗滑入的新元素記為x、滑出的舊元素記為z，則Q的更新步驟為：

執行以上操作後，Q的隊首元素即為當前滑動視窗最大值。過程如圖所示：

空間上，需要額外的空間儲存Q，Q的最大長度不超過K，因此空間複雜度是O(K)。

時間上，共迭代了N次，每次需要對Q做壓入和彈出操作。最差的情況，某次迭代會彈出Q所有元素。Q的長度最大為K，所以貌似時間代價是O(NK)；但實際上，從整體看，所有的元素都會壓入一次，彈出一次，所以實際複雜度其實為O(N)。

演演算法每次迭代都維持了一個條件不變式:

例如上圖中，

值得注意的是，如果最大的元素存在多個，則認為是它們中的第一個。

按照上文的更新規則，更新過程可以表述為：

我們先來關注過程一。過程一可能有幾個情況：

Case 1: x擠掉了Q的所有元素，說明它大於Q中所有元素，此時Q中只剩下x，顯然這時候滿足條件二。

Case 2: x沒有擠掉任何Q的元素，說明x小於等於Q的所有元素。此時x會追加到Q的尾部，顯然這時候滿足條件二。

Case 3：x擠掉了Q的一部分元素，說明x大於Q尾部的一個或多個元素。

我們假設

\[q_k \ge x > \{ q_{k+1},...,q_m \} \]

則x會擠掉原來的 \(\{ q_{k+1},...,q_m \}\) 成為新的\(q_{k+1}\)。

此時條件二成立：x比\(q_0\)小，不會動搖它的地位；x比\(q_{k+1}\)大，而後者是W中\(q_k\)之後最大的元素，因此x自然也是\(q_k\)之後最大的元素，那麼x成為新的\(q_{k+1}\)後，自然滿足條件二。

此時我們關注過程一。如果滑窗彈出的元素就是\(q_0\)，那麼Q自然也應該彈出\(q_0\)，這樣才能滿足條件一。

如果W彈出的元素z不等於\(q_0\)，那麼無需處理，如下圖中情況(a)所示。
如果z等於\(q_0\)，那麼可以確定彈出的就是\(q_0\)，畢竟\(q_0\)是W中的最大元素(如果最大元素有多個則為第一個)。此時W和Q都彈出\(q_0\)後，依然符合條件一和條件二，這裡不再證明。情況如下圖(b)所示。

至此，證明完畢。

我們可以簡單理解一下：Q是W的子序列，當W失去元素z時，Q自然也要失去它；如果W新來了一個很大的元素x，那麼直到它被彈出之前，在前面比它小的元素是沒有出頭之日的。在它彈出之後，它前面的元素自然也早被彈出了。所以在前面比它小的元素都沒有用，可以即刻彈出。