Java 滑動(dòng)窗口最大值的實(shí)現

一、題目

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

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

二、單調隊列解析

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

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

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

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

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

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

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

三、代碼

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

四、總結

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

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

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

到此這篇關(guān)于Java 滑動(dòng)窗口最大值的實(shí)現的文章就介紹到這了,更多相關(guān)Java 滑動(dòng)窗口最大值內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！