給你一個整數數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。

返回滑動窗口中的最大值。

題目讓求隨著滑動窗口的滑動，返回窗口覆蓋范圍的最大值

該題不適合優(yōu)先級隊列，因為采用大頂堆存放k個數字，可以知道此時的最大值，但是窗口是滑動的，大頂堆每次只能彈出最大值，無法移除其他值，即無法用大頂堆維護滑動窗口里的值。

所以采用隊列維護，隨著窗口的移動，隊列先進先出

此時對隊列的要求是，隊列首位為最大值，整個隊列呈遞減例如：1,3,-1,-3,5,3,6,7

初始：1,3,-1，隊列存入3,-1，使其保持遞減，且首位為此時滑動窗口的最大值移動到-3，隊列：3,-1,-3移動到5，隊列：5移動到3，隊列：5,3移動到6，隊列：6移動到7，隊列：7

所以為了滿足要求，需要自定義隊列

從示例可以看出，隊列沒必要維護窗口里所有元素，只需要保證隊列首位此時窗口的最大，而且，隊列元素為遞減，具體看代碼

import java.util.Deque;import java.util.LinkedList;//自定義數組class MyQueue { Deque<Integer> deque = new LinkedList<>(); //彈出元素時，比較當前要彈出的數值是否等于隊列出口的數值，如果相等則彈出 //同時判斷隊列當前是否為空 void poll(int val) {if (!deque.isEmpty() && val == deque.peek()) { deque.poll();} } //添加元素時，如果要添加的元素大于入口處的元素，就將入口元素彈出 //保證隊列元素單調遞減 //比如此時隊列元素3,1，2將要入隊，比1大，所以1彈出，此時隊列：3,2 void add(int val) {while (!deque.isEmpty() && val > deque.getLast()) { deque.removeLast();}deque.add(val); } //隊列隊頂元素始終為最大值 int peek() {return deque.peek(); }}class Solution { public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length == 1) { return nums;}int len = nums.length - k + 1;//存放結果元素的數組int[] res = new int[len];int num = 0;//自定義隊列MyQueue myQueue = new MyQueue();//先將前k的元素放入隊列for (int i = 0; i < k; i++) { myQueue.add(nums[i]);}res[num++] = myQueue.peek();for (int i = k; i < nums.length; i++) { //滑動窗口移除最前面的元素，移除是判斷該元素是否放入隊列 myQueue.poll(nums[i - k]); //滑動窗口加入最后面的元素 myQueue.add(nums[i]); //記錄對應的最大值 res[num++] = myQueue.peek();}return res; }}四、總結

該題利用了單調隊列，需要自己定義入隊出隊規(guī)則

入隊：保持隊首元素始終最大，同時隊內維護窗口的大小個元素，呈現遞減

出隊：判斷當前元素是否入隊，在隊內，再隨著窗口的滑動執(zhí)行出隊操作

到此這篇關于Java 滑動窗口最大值的實現的文章就介紹到這了,更多相關Java 滑動窗口最大值內容請搜索好吧啦網以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持好吧啦網！