給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口中的最大值。

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

該題不適合優(yōu)先級(jí)隊(duì)列，因?yàn)椴捎么箜敹汛娣舓個(gè)數(shù)字，可以知道此時(shí)的最大值，但是窗口是滑動(dòng)的，大頂堆每次只能彈出最大值，無(wú)法移除其他值，即無(wú)法用大頂堆維護(hù)滑動(dòng)窗口里的值。

所以采用隊(duì)列維護(hù)，隨著窗口的移動(dòng)，隊(duì)列先進(jìn)先出

此時(shí)對(duì)隊(duì)列的要求是，隊(duì)列首位為最大值，整個(gè)隊(duì)列呈遞減例如：1,3,-1,-3,5,3,6,7

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

所以為了滿(mǎn)足要求，需要自定義隊(duì)列

從示例可以看出，隊(duì)列沒(méi)必要維護(hù)窗口里所有元素，只需要保證隊(duì)列首位此時(shí)窗口的最大，而且，隊(duì)列元素為遞減，具體看代碼

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

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

入隊(duì)：保持隊(duì)首元素始終最大，同時(shí)隊(duì)內(nèi)維護(hù)窗口的大小個(gè)元素，呈現(xiàn)遞減

出隊(duì)：判斷當(dāng)前元素是否入隊(duì)，在隊(duì)內(nèi)，再隨著窗口的滑動(dòng)執(zhí)行出隊(duì)操作

到此這篇關(guān)于Java 滑動(dòng)窗口最大值的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java 滑動(dòng)窗口最大值內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！