LeetCode如何找出隊列的最大值和滑動窗口的最大值

題目介紹

給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}；針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個：{[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

解題思路

方法一：蠻力法

思路

掃描窗口k，得到最大值。對于長度為n的數(shù)組，算法時間復雜度O（nk）

顯然不是最優(yōu)解。

方法二：用兩個棧實現(xiàn)隊列

思路

面試題30中，我們實現(xiàn)過用兩個棧實現(xiàn)了隊列，可以在O（1）時間得到棧的最大值，也就可以得到隊列的最大值。

這樣總的時間復雜度O（n）

但是這樣的思路寫代碼，等于同時要寫兩個題目，面試時間可能不允許。

方法三：雙端隊列

思路

參考解釋：

https://cuijiahua.com/blog/2018/02/basis_64.html

數(shù)組的第一個數(shù)字是2，把它存入隊列中。第二個數(shù)字是3，比2大，所以2不可能是滑動窗口中的最大值，因此把2從隊列里刪除，再把3存入隊列中。第三個數(shù)字是4，比3大，同樣的刪3存4。此時滑動窗口中已經有3個數(shù)字，而它的最大值4位于隊列的頭部。

第四個數(shù)字2比4小，但是當4滑出之后它還是有可能成為最大值的，所以我們把2存入隊列的尾部。下一個數(shù)字是6，比4和2都大，刪4和2，存6。就這樣依次進行，最大值永遠位于隊列的頭部。

但是我們怎樣判斷滑動窗口是否包括一個數(shù)字？應該在隊列里存入數(shù)字在數(shù)組里的下標，而不是數(shù)值。當一個數(shù)字的下標與當前處理的數(shù)字的下標之差大于或者相等于滑動窗口大小時，這個數(shù)字已經從窗口中滑出，可以從隊列頭部把它刪除。因此，我們既有可能從頭部刪除數(shù)字，又可能從尾部刪除數(shù)字，所以要雙端隊列。

 

代碼

注意點：

• ArrayDeque的幾個API：pollFirst、peekFirst等

• ArrayDeque保存的是下標

• 最新的數(shù)的下標是必定加進去的。

import java.util.ArrayList;
import java.util.ArrayDeque;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> result = new ArrayList<>();
        // 排除特殊情況，窗口的長度為0
        if (size==0) return result;

        // 滑動窗口最左邊數(shù)的index
        int begin;
        // 建立一個雙端隊列
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for(int i=0;i<num.length;i++){
            // begin是窗口起始位置
            begin = i-size+1;
            // 隊列空，直接加入
            if(q.isEmpty())
                q.add(i);
            // 若隊列最左邊值已經不在窗口內，直接刪除
            else if(begin > q.peekFirst())
                q.pollFirst();

            // 從隊尾開始比較，把所有比他小的值丟掉
            while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
            // 隨后再把它放進去
            q.add(i);

            // 若窗口起始位置在數(shù)組的0位置上或者之后（窗口是完整大小的），才計算窗口的有效最大值
            if(begin>=0){
                // 永遠是隊列最左邊最大，加入結果集
                result.add(num[q.peekFirst()]);
            }
        }
        return result;
    }
}