題目介紹

給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}；針對數組{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的數組，算法時間復雜度O（nk）

顯然不是最優解。

方法二：用兩個棧實現隊列

思路

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

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

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

方法三：雙端隊列

思路

參考解釋：

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

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

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

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

 

代碼

注意點：

• ArrayDeque的幾個API：pollFirst、peekFirst等

• ArrayDeque保存的是下標

• 最新的數的下標是必定加進去的。

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;

        // 滑動窗口最左邊數的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);

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