力扣題目鏈接

?

(opens new window)

給定一個(gè)數(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)窗口中的最大值。

進(jìn)階：

你能在線性時(shí)間復(fù)雜度內(nèi)解決此題嗎？

提示：

• 1 <= nums.length <= 10^5
• -10^4?<= nums[i]?<= 10^4
• 1 <= k?<= nums.length

代碼文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-609008.html

//解法一
//自定義數(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;
    }
}

//解法二
//利用雙端隊(duì)列手動(dòng)實(shí)現(xiàn)單調(diào)隊(duì)列
/**
 * 用一個(gè)單調(diào)隊(duì)列來(lái)存儲(chǔ)對(duì)應(yīng)的下標(biāo)，每當(dāng)窗口滑動(dòng)的時(shí)候，直接取隊(duì)列的頭部指針對(duì)應(yīng)的值放入結(jié)果集即可
 * 單調(diào)隊(duì)列類似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右邊為頭結(jié)點(diǎn)，元素存的是下標(biāo))
 */
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for(int i = 0; i < n; i++) {
            // 根據(jù)題意，i為nums下標(biāo)，是要在[i - k + 1, i] 中選到最大值，只需要保證兩點(diǎn)
            // 1.隊(duì)列頭結(jié)點(diǎn)需要在[i - k + 1, i]范圍內(nèi)，不符合則要彈出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.既然是單調(diào)，就要保證每次放進(jìn)去的數(shù)字要比末尾的都大，否則也彈出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因?yàn)閱握{(diào)，當(dāng)i增長(zhǎng)到符合第一個(gè)k范圍的時(shí)候，每滑動(dòng)一步都將隊(duì)列頭節(jié)點(diǎn)放入結(jié)果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

到了這里，關(guān)于239. 滑動(dòng)窗口最大值的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！