作者 | 王磊

來源 | Java中文社群（ID：javacn666）

轉(zhuǎn)載請聯(lián)系授權(quán)（微信ID：GG_Stone）

本文已收錄至 Github《小白學算法》系列：https://github.com/vipstone/algorithm

這是一道比較基礎的算法題，涉及到的數(shù)據(jù)結(jié)構(gòu)也是我們之前講過的，我這里先買一個關子。這道面試題最近半年在亞馬遜的面試中出現(xiàn)過 28 次，在字節(jié)跳動中出現(xiàn)過 7 次，數(shù)據(jù)來源于 LeetCode。

我們先來看題目的描述。

題目描述

給定一個數(shù)組 nums 和滑動窗口的大小 k，請找出所有滑動窗口里的最大值。

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 輸出: [3,3,5,5,6,7]

提示：你可以假設 k 總是有效的，在輸入數(shù)組不為空的情況下，1 ≤ k ≤?輸入數(shù)組的大小。

LeetCode：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

題目解析

上面的題目看不懂？沒關系，接下來來看這幅圖可以清楚的描述這道題：從上述圖片可以看出，題目的意思為：給定一個數(shù)組，每次查詢 3 個元素中的最大值，數(shù)量 3 為滑動窗口的大小，之后依次向后移動查詢相鄰 3 個元素的最大值。圖片中的原始數(shù)組為 [1,3,-1,-3,5,3,6,7]，最終滑動窗口的最大值為 [3,3,5,5,6,7]。

看到這個題之后，我們的第一直覺就是暴力解法，用兩層循環(huán)依次查詢滑動窗口的最大值，實現(xiàn)代碼如下。

實現(xiàn)方法 1：暴力解法

暴力解法的實現(xiàn)思路和實現(xiàn)代碼很直觀，如下所示：

class?Solution?{public?int[]?maxSlidingWindow(int[]?nums,?int?k)?{//?非空判斷if?(nums?==?null?||?k?<=?0)?return?new?int[0];//?最終結(jié)果數(shù)組int[]?res?=?new?int[nums.length?-?k?+?1];for?(int?i?=?0;?i?<?res.length;?i++)?{//?初始化最大值int?max?=?nums[i];?//?循環(huán)?k-1?次找最大值for?(int?j?=?i?+?1;?j?<?(i?+?k);?j++)?{max?=?(nums[j]?>?max)???nums[j]?:?max;}res[i]?=?max;}return?res;} }

把以上代碼提交至 LeetCode，執(zhí)行結(jié)果如下：從上述結(jié)果可以看出，雖然代碼通過了測試，但執(zhí)行效率卻很低，這種代碼是不能應用于生產(chǎn)環(huán)境中的，因此我們需要繼續(xù)找尋新的解決方案。

實現(xiàn)方法 2：改良版

接下來我們稍微優(yōu)化一下上面的方法，其實我們并不需要每次都經(jīng)過兩層循環(huán)，我們只需要一層循環(huán)拿到滑動窗口的最大值（之前循環(huán)元素的最大值），然后在移除元素時，判斷當前要移除的元素是否為滑動窗口的最大值，如果是，則進行第二層循環(huán)來找到新的滑動窗口的最大值，否則只需要將最大值和新增的元素比較大小即可，實現(xiàn)代碼如下：

class?Solution?{public?int[]?maxSlidingWindow(int[]?nums,?int?k)?{//?非空判斷if?(nums?==?null?||?k?<=?0)?return?new?int[0];//?最終結(jié)果數(shù)組int[]?res?=?new?int[nums.length?-?k?+?1];//?上一輪循環(huán)移除的值int?r?=?-Integer.MAX_VALUE;?//?滑動窗口最大值（初始化）int?max?=?r;?for?(int?i?=?0;?i?<?res.length;?i++)?{//?1.判斷移除的值，是否為滑動窗口的最大值if?(r?==?max)?{//?2.移除的是滑動窗口的最大值，循環(huán)找到新的滑動窗口的最大值max?=?nums[i];?//?初始化最大值//?循環(huán)找最大值for?(int?j?=?i?+?1;?j?<?(i?+?k);?j++)?{max?=?Math.max(max,?nums[j]);}}?else?{//?3.只需要用滑動窗口的最大值和新增值比較即可max?=?Math.max(max,?nums[i?+?k?-?1]);}//?最終的返回數(shù)組記錄res[i]?=?max;//?記錄下輪要移除的元素r?=?nums[i];}return?res;} }

把以上代碼提交至 LeetCode，執(zhí)行結(jié)果如下：從上述結(jié)果可以看出，改造之后的性能基本已經(jīng)符合我的要求了，那文章開頭說過這道題還可以使用我們之前學過的數(shù)據(jù)結(jié)構(gòu)？那它說的是什么數(shù)據(jù)結(jié)構(gòu)呢？

其實我們可以使用「隊列」來實現(xiàn)這道題目，它的實現(xiàn)思路也非常簡單，甚至比暴力解法更加方便，接下來我們繼續(xù)往下看。

實現(xiàn)方法 3：優(yōu)先隊列

這個題的另一種經(jīng)典的解法，就是使用最大堆的方式來解決，最大堆的結(jié)構(gòu)如下所示：最大堆的特性是堆頂是整個堆中最大的元素。

我們可以將滑動窗口的值放入最大堆中，這樣利用此數(shù)據(jù)結(jié)構(gòu)的特點（它會將最大值放到堆頂），因此我們就可以直接獲取到滑動窗口的最大值了，實現(xiàn)代碼如下：

class?Solution?{public?int[]?maxSlidingWindow(int[]?nums,?int?k)?{//?非空判斷if?(nums?==?null?||?k?<=?0)?return?new?int[]{};//?最終結(jié)果數(shù)組int[]?res?=?new?int[nums.length?-?k?+?1];//?優(yōu)先隊列PriorityQueue<Integer>?queue?=?new?PriorityQueue(res.length,?new?Comparator<Integer>()?{@Overridepublic?int?compare(Integer?i1,?Integer?i2)?{//?倒序排列（從大到小，默認是從小到大）return?i2?-?i1;}});//?第一輪元素添加for?(int?i?=?0;?i?<?k;?i++)?{queue.offer(nums[i]);}res[0]?=?queue.peek();int?last?=?nums[0];?//?每輪要移除的元素for?(int?i?=?k;?i?<?nums.length;?i++)?{//?移除滑動窗口之外的元素queue.remove(last);//?添加新元素queue.offer(nums[i]);//?存入最大值res[i?-?k?+?1]?=?queue.peek();//?記錄每輪要移除的元素（滑動窗口最左邊的元素）last?=?nums[i?-?k?+?1];}return?res;} }

代碼解讀

從上述代碼可以看出：最大堆在 Java 中對應的數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列 PriorityQueue，但優(yōu)先級隊列默認的排序規(guī)則是從小到大進行排序的，因此我們需要創(chuàng)建一個 Comparator?來改變一下排序的規(guī)則（從大到小進行排序），之后將滑動窗口的所有元素放入到優(yōu)先級隊列中，這樣我們就可以直接使用 queue.peek()?拿到滑動窗口的最大值了，然后再循環(huán)將滑動窗口的邊緣值移除掉，從而解決了本道題目。

把以上代碼提交至 LeetCode，執(zhí)行結(jié)果如下：

PS：從上面的執(zhí)行結(jié)果可以看出，使用優(yōu)先隊列的執(zhí)行效率很低，這是因為每次插入和刪除都需要重新維護最大堆的元素順序，因此整個執(zhí)行的效率就會很低。

實現(xiàn)方法 4：雙端隊列

除了優(yōu)先隊列之外，我們還可以使用雙端隊列來查詢滑動窗口的最大值，它的實現(xiàn)思路和最大堆的實現(xiàn)思路很像，但并不需要每次在添加和刪除時進行元素位置的維護，因此它的執(zhí)行效率會很高。

雙端隊列實現(xiàn)思路的核心是將滑動窗口的最大值始終放在隊首位置（也就是隊列的最左邊），將小于最大值并在最大值左邊（隊首方向）的所有元素刪除。這個也很好理解，因為這些相對較小的值既沒有最大值大，又在最大值的前面，也就是它們的生命周期比最大值還短，因此我們可以直接將這些相對較小的元素進行刪除，如下圖所示：

像以上這種情況下，我們就可以將元素 1 和元素 2 刪掉。

雙端隊列實現(xiàn)查詢滑動窗口最大值的流程分為以下 4 步：

移除最左邊小于最大值的元素（保證滑動窗口的最大值在隊首位置）；

從隊尾向前依次移除小于當前要加入到隊列元素的值（淘汰小值且生命周期短的元素）；

將新元素加入到隊列末尾；

將最大值加入到最終結(jié)果的數(shù)組中。

實現(xiàn)代碼如下：

class?Solution?{public?int[]?maxSlidingWindow(int[]?nums,?int?k)?{//?非空判斷if?(nums?==?null?||?k?<=?0)?return?new?int[0];//?最終結(jié)果數(shù)組int[]?res?=?new?int[nums.length?-?k?+?1];//?存儲的數(shù)據(jù)為元素的下標ArrayDeque<Integer>?deque?=?new?ArrayDeque();for?(int?i?=?0;?i?<?nums.length;?i++)?{//?1.移除左邊超過滑動窗口的下標if?(i?>=?k?&&?(i?-?k)?>=?deque.peek())?deque.removeFirst();//?2.從最后面開始移除小于?nums[i]?的元素while?(!deque.isEmpty()?&&?nums[deque.peekLast()]?<?nums[i])deque.removeLast();//?3.下標加入隊列deque.offer(i);//?4.將最大值加入數(shù)組int?rindex?=?i?-?k?+?1;if?(rindex?>=?0)?{res[rindex]?=?nums[deque.peek()];}}return?res;} }

把以上代碼提交至 LeetCode，執(zhí)行結(jié)果如下：

從上述結(jié)果可以看出，雙端隊列相比于優(yōu)先級隊列來說，因為無需重新計算并維護元素的位置，所以執(zhí)行效率還是挺高的。

總結(jié)

本文我們通過 4 種方式實現(xiàn)了查找滑動窗口最大值的功能，其中暴力解法通過兩層循環(huán)來實現(xiàn)此功能，代碼最簡單但執(zhí)行效率不高，而通過最大堆也就是優(yōu)先隊列的方式來實現(xiàn)（本題）雖然比較省事，但執(zhí)行效率不高。因此我們可以選擇使用雙端隊列或改良版的代碼來實現(xiàn)查詢滑動窗口的最大值。

往期推薦

真不錯，圖解Java中的5大隊列！

23張圖！萬字詳解「鏈表」，從小白到大佬！

隊列實現(xiàn)棧的3種方法，全都擊敗了100%的用戶！

關注我，每天陪你進步一點點！

總結(jié)

以上是生活随笔為你收集整理的嗯，查询滑动窗口最大值的这4种方法不错....的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。