給定一個數(shù)組 nums，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口 k 內(nèi)的數(shù)字?；瑒哟翱诿看沃幌蛴乙苿右晃弧?/p>

返回滑動窗口最大值。

示例:

輸入: 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
注意：

你可以假設(shè) k 總是有效的，1 ≤ k ≤ 輸入數(shù)組的大小，且輸入數(shù)組不為空。

思路

定義一個雙端隊列MyDeque類，將這隊列作為滑動窗口，先向隊列填窗口前k-1個數(shù)，push方法每添加一個數(shù)會先判斷，后添加的數(shù)如果大于之前添加，會將之前添加的數(shù)刪除，可以認(rèn)為后來的數(shù)壓扁錢前面的數(shù)，則當(dāng)前組的最大值就是隊頭，往下滑動，要刪除窗口的第一個數(shù)，這里需要判斷，這第一個數(shù)可能已經(jīng)后來的數(shù)壓扁，如果沒有壓扁，則需要刪除(因為滑動窗口向右滑動，前面刪除一個數(shù)，后面增加一個數(shù))

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {   
        MyDeque myDeque = new MyDeque();
        int res[] = {};
        if (nums == null || nums.length == 0) {
            return res;   
        } else {
            res = new int[nums.length - k + 1];
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                myDeque.push(nums[i]);
            } else {
                myDeque.push(nums[i]);
                res[j++] = myDeque.max();
                myDeque.pop(nums[i - k + 1]);
            }
        }
        return res;
    }
class MyDeque {

    private Deque<Integer> deque;

    public MyDeque() {
        deque = new LinkedList<Integer>();
    }

    void push(int n) {
        while ((!deque.isEmpty()) && deque.getLast() < n) {
            deque.removeLast();
        }
        deque.addLast(n);
    }

    void pop(int n) {
        if ((!deque.isEmpty()) && deque.getFirst() == n) {
            deque.removeFirst();
        }
        
    }

    int max() {
        return deque.getFirst();
    }
}