滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 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 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

思路

定义一个双端队列MyDeque类，将这队列作为滑动窗口，先向队列填窗口前k-1个数，push方法每添加一个数会先判断，后添加的数如果大于之前添加，会将之前添加的数删除，可以认为后来的数压扁钱前面的数，则当前组的最大值就是队头，往下滑动，要删除窗口的第一个数，这里需要判断，这第一个数可能已经后来的数压扁，如果没有压扁，则需要删除(因为滑动窗口向右滑动，前面删除一个数，后面增加一个数)

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();
    }
}