239.滑动窗口最大值 (opens new window)

核心思想就是利用双端队列，去实现单调队列一样的操作。只需要维护滑动窗口中可能会成为最大值的数字。

然后再下一次移动的时候，进行先弹出被滑动出去的值，后添加新滑进窗口的值

弹出的操作，只需要判断被弹出的值是否等于队列头，如果等于就弹出，反之则无需操作

添加值进队列，只要队列尾是小于被加入的值，就从末尾弹出。直到队列为空或者队列尾部的值更大。

class Solution {
    /**
     * @param nums 数组
     * @param k 滑动窗口的大小
     * @return 返回一个数据，表明滑动窗口中的最大值
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>(); //声明队列
        int[] result = new int[nums.length-k+1];
        for (int i = 0; i < k; i++) {
            push(deque,nums[i]);
        }
        int num = 0;
        result[num++] = deque.peek();
        int i = k;
        while (i<nums.length){
                //弹出最左边的元素
                pop(deque,nums[i-k]);
                //加入最右边的元素
                push(deque,nums[i]);
            result[num++] = deque.peek();
            i++;
        }
        return result;
    }

    /**
     * 往队列插入数据,如果num比末尾大，则弹出全部，再插入
     * 否则直接插入
     * @param deque
     * @param num
     */
    private void push(Deque<Integer> deque, int num){
        while (!deque.isEmpty() && deque.getLast() <num){
            deque.pollLast();
        }
        deque.addLast(num);
    }

    /**
     * 往队列插入数据,如果num比末尾大，则弹出全部，再插入
     * 否则直接插入
     * @param deque
     * @param num
     */
    private void pop(Deque<Integer> deque, int num){
        if (!deque.isEmpty() && deque.peek()==num){
            deque.pop();
        }
    }

}