本文已收錄至 Github《小白學算法》系列：https://github.com/vipstone/algorithm
這是一道比較基礎的算法題，涉及到的資料結構也是我們之前講過的，我這裡先買一個關子。這道面試題最近半年在亞馬遜的面試中出現過 28 次，在位元組跳動中出現過 7 次，資料來源于 LeetCode。
我們先來看題目的描述。
給定一個數組 nums 和滑動視窗的大小 k，請找出所有滑動視窗裡的最大值。
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 輸出: [3,3,5,5,6,7]
提示：
你可以假設 k 總是有效的，在輸入數組不為空的情況下，1 ≤ k ≤ 輸入數組的大小。
LeetCode：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
上面的題目看不懂？沒關系，接下來來看這幅圖可以清楚的描述這道題：
從上述圖檔可以看出，題目的意思為：給定一個數組，每次查詢 3 個元素中的最大值，數量 3 為滑動視窗的大小，之後依次向後移動查詢相鄰 3 個元素的最大值。圖檔中的原始數組為 <code>[1,3,-1,-3,5,3,6,7]</code>，最終滑動視窗的最大值為 <code>[3,3,5,5,6,7]</code>。
看到這個題之後，我們的第一直覺就是暴力解法，用兩層循環依次查詢滑動視窗的最大值，實作代碼如下。
暴力解法的實作思路和實作代碼很直覺，如下所示：
把以上代碼送出至 LeetCode，執行結果如下：
從上述結果可以看出，雖然代碼通過了測試，但執行效率卻很低，這種代碼是不能應用于生産環境中的，是以我們需要繼續找尋新的解決方案。
接下來我們稍微優化一下上面的方法，其實我們并不需要每次都經過兩層循環，我們隻需要一層循環拿到滑動視窗的最大值（之前循環元素的最大值），然後在移除元素時，判斷目前要移除的元素是否為滑動視窗的最大值，如果是，則進行第二層循環來找到新的滑動視窗的最大值，否則隻需要将最大值和新增的元素比較大小即可，實作代碼如下：
從上述結果可以看出，改造之後的性能基本已經符合我的要求了，那文章開頭說過這道題還可以使用我們之前學過的資料結構？那它說的是什麼資料結構呢？
其實我們可以使用「隊列」來實作這道題目，它的實作思路也非常簡單，甚至比暴力解法更加友善，接下來我們繼續往下看。
這個題的另一種經典的解法，就是使用最大堆的方式來解決，最大堆的結構如下所示：
最大堆的特性是堆頂是整個堆中最大的元素。
我們可以将滑動視窗的值放入最大堆中，這樣利用此資料結構的特點（它會将最大值放到堆頂），是以我們就可以直接擷取到滑動視窗的最大值了，實作代碼如下：
從上述代碼可以看出：最大堆在 Java 中對應的資料結構就是優先級隊列 <code>PriorityQueue</code>，但優先級隊列預設的排序規則是從小到大進行排序的，是以我們需要建立一個 <code>Comparator</code> 來改變一下排序的規則（從大到小進行排序），之後将滑動視窗的所有元素放入到優先級隊列中，這樣我們就可以直接使用 <code>queue.peek()</code> 拿到滑動視窗的最大值了，然後再循環将滑動視窗的邊緣值移除掉，進而解決了本道題目。
PS：從上面的執行結果可以看出，使用優先隊列的執行效率很低，這是因為每次插入和删除都需要重新維護最大堆的元素順序，是以整個執行的效率就會很低。
除了優先隊列之外，我們還可以使用雙端隊列來查詢滑動視窗的最大值，它的實作思路和最大堆的實作思路很像，但并不需要每次在添加和删除時進行元素位置的維護，是以它的執行效率會很高。
雙端隊列實作思路的核心是将滑動視窗的最大值始終放在隊首位置（也就是隊列的最左邊），将小于最大值并在最大值左邊（隊首方向）的所有元素删除。這個也很好了解，因為這些相對較小的值既沒有最大值大，又在最大值的前面，也就是它們的生命周期比最大值還短，是以我們可以直接将這些相對較小的元素進行删除，如下圖所示：
像以上這種情況下，我們就可以将元素 1 和元素 2 删掉。
雙端隊列實作查詢滑動視窗最大值的流程分為以下 4 步：
移除最左邊小于最大值的元素（保證滑動視窗的最大值在隊首位置）；
從隊尾向前依次移除小于目前要加入到隊列元素的值（淘汰小值且生命周期短的元素）；
将新元素加入到隊列末尾；
将最大值加入到最終結果的數組中。
實作代碼如下：
從上述結果可以看出，雙端隊列相比于優先級隊列來說，因為無需重新計算并維護元素的位置，是以執行效率還是挺高的。
本文我們通過 4 種方式實作了查找滑動視窗最大值的功能，其中暴力解法通過兩層循環來實作此功能，代碼最簡單但執行效率不高，而通過最大堆也就是優先隊列的方式來實作（本題）雖然比較省事，但執行效率不高。是以我們可以選擇使用雙端隊列或改良版的代碼來實作查詢滑動視窗的最大值。
關注下面二維碼，訂閱更多精彩内容。
關注公衆号（加好友）：
作者：
王磊的部落格
出處：
http://vipstone.cnblogs.com/