問題描述

給定一個陣列 nums 和滑動視窗的大小 k，請找出所有滑動視窗里的最大值，

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7] 
解釋: 

  滑動視窗的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

解題思路

本題可以采用暴力方法求解，每次滑動視窗所移動到的k個數中求最大值，那么每次需要O(k)個時間，一共n步，則O(nk)
當然也可以用單調佇列進行求解,單調佇列與單調堆疊問題相類似，單調堆疊問題參看包含min函式的堆疊(單調堆疊)

單調佇列與單調堆疊問題類似，我們可以觀察佇列里面是否有一些元素是沒有用的，我們把這些沒有用的元素去掉的話，看看是否會得到單調性，
如上圖為例，假設我們每次求的是滑動視窗中的最小值，當-3進來之后，第一個3肯定沒有用，我們每次求的是佇列中最小值，-3小于3,3是在-3的左邊，所以說，這個3會被先彈出去，換句話說，只要-3在，3就永遠不會被當成最小值輸出，并且-3還活的更久一點，它會在3被移出滑動視窗之后才會被移出去，因此我們就可以斷定前面的3一定不會被當成答案輸出出來，就可以去掉，同樣，-1也是如此，
因此，只要佇列里面存在前面一個數比后面的數還要大，那么前面的數就肯定沒有用，因為后面的數會后被彈出來，而且更小，因此，只要有這樣的逆序對的話，我們就可以把大的點刪掉，我們把所有這樣的數都刪掉，整個佇列就會變成嚴格單調上升的佇列了，
我們要求佇列中的最小值，那么嚴格單調上升的佇列就是隊頭元素，所以每次找最小值的時候，直接找隊頭元素即可，
總結：單調堆疊和單調佇列的問題，我們可以先考慮用堆疊和佇列來暴力的模擬原來的問題，即常規思路，然后再看看常規思路里面，堆疊和佇列中哪些元素是沒有用的，然后再刪掉，看看剩下的元素是否有單調性，如果剩下的元素有單調性，就可以做一些優化，如取極值或者二分，

而對于本題而言：

由于我們需要求出的是滑動視窗的最大值，如果當前的滑動視窗中有兩個下標 i 和 j，其中 i 在 j 的左側（i < j），并且 i對應的元素不大于 j對應的元素即（nums[i]<=nums[j]），那么會發生什么呢？

當滑動視窗向右移動時，只要 i 還在視窗中，那么 j 一定也還在視窗中，這是 i 在 j的左側所保證的，因此，由于nums[j] 的存在，nums[i] 一定不會是滑動視窗中的最大值了，我們可以將nums[i] 永久地移除

因此我們可以使用一個佇列存盤所有還沒有被移除的下標，在佇列中，這些下標按照從小到大的順序被存盤，并且它們在陣列 nums 中對應的值是嚴格單調遞減的，因為如果佇列中有兩個相鄰的下標，它們對應的值相等或者遞增，那么令前者為 i，后者為 j，就對應了上面所說的情況，即nums[i] 會被移除，這就產生了矛盾，

當滑動視窗向右移動時，我們需要把一個新的元素放入佇列中，為了保持佇列的性質，我們會不斷地將新的元素與隊尾的元素相比較，如果前者大于等于后者，那么隊尾的元素就可以被永久地移除，我們將其彈出佇列，我們需要不斷地進行此項操作，直到佇列為慷訓者新的元素小于隊尾的元素，

**由于佇列中下標對應的元素是嚴格單調遞減的，因此此時隊首下標對應的元素就是滑動視窗中的最大值，**但與方法一中相同的是，此時的最大值可能在滑動視窗左邊界的左側，并且隨著視窗向右移動，它永遠不可能出現在滑動視窗中了，因此我們還需要不斷從隊首彈出元素，直到隊首元素在視窗中為止，

為了可以同時彈出隊首和隊尾的元素，我們需要使用雙端佇列，滿足這種單調性的雙端佇列一般稱作「單調佇列」，

在Java中，雙端佇列及其應用可以參考Java雙端佇列Deque及其應用

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len=nums.length;
        if(len<1){
            return nums;
        }
        //創建雙端佇列，使用LinkedList實作類
        //注意，雙端佇列存盤的是元素的下標
        Deque<Integer> queue=new LinkedList<Integer>();
        List<Integer> list=new ArrayList<Integer>();        //用于保存最終結果
        int st=0,ed=k-1;        //st,ed分別指向滑動視窗的左右邊界
        //我們先把初始情況下滑動視窗里面的元素都加入到單調佇列中，這里隱含了k>=len的問題
        for(int i=st;i<=ed;i++){    
            //當滑動視窗右移時，會不斷判斷當前元素是否大于或者等于隊尾元素對應的值，如果滿足條件的話，就移出隊尾元素
            //一直到佇列為慷訓者當前元素小于隊尾元素對應的值為止
            //才把當前元素的下標加入到隊尾，這樣可以保持佇列的單調遞減的性質
            while(!queue.isEmpty() && nums[i]>=nums[queue.peekLast()]){
                int temp=queue.pollLast();
            } 
            queue.offerLast(i);
        }
        //把隊頭元素加入到結果集中，隊頭元素對應的值即滑動視窗的最大值
        list.add(nums[queue.peekFirst()]);
        while(ed<len-1){
            //滑動視窗后移一位
            st++;
            ed++;
            //當佇列不為空，并且隊頭元素（下標）處在滑動視窗左端點的左邊時，就需要把它移出佇列
            if(!queue.isEmpty() && queue.peekFirst()<st){
                int temp=queue.pollFirst();
            }
            //當滑動視窗右移時，會不斷判斷當前元素是否大于或者等于隊尾元素對應的值，如果滿足條件的話，就移出隊尾元素
            //一直到佇列為慷訓者當前元素小于隊尾元素對應的值為止
            //才把當前元素的下標加入到隊尾，這樣可以保持佇列的單調遞減的性質   
            while(!queue.isEmpty() && nums[ed]>=nums[queue.peekLast()]){
                int temp=queue.pollLast();
            }
            queue.offerLast(ed);
            list.add(nums[queue.peekFirst()]);
        }
        //把結果存入到陣列中
        int size=list.size();
        int res[]=new int[size];
        for(int i=0;i<size;i++){
            res[i]=list.get(i);
        }
        return res;
    }
}