1、前言

2、思路

如果本题直接使用优先队列，在找最大值时比较方便，但是删除窗口的值很麻烦，每次都需要遍历堆中的值，最后会超时。

其实此题主要是利用原来 minStack 的思路。minStack 保证栈顶一定是栈中的最小值，那我们可以定义一个双端队列，队列保持递减，所以对首总是最大的。

算法流程：
1）push 数进队列的时候，要保证队列尾开始的数比它大，否则一直移出队尾的数，直到符合条件，然后把此数放入队尾。
2）pop 队列的时候，如果要 pop 的值与队首相等，那么要把队首的值 pop 掉。

3、代码

class Solution {

    class MaxQueue{
        private Deque<Integer> queue = new LinkedList<>();

        public void push(int n){
            while(!queue.isEmpty() && queue.peekLast() < n){
                queue.pollLast();
            }
            queue.addLast(n);
        }

        public void pop(int n){
            if(queue.peekFirst() == n){
                queue.pollFirst();
            }
        }

        public int max(){
            return queue.peekFirst();
        }
    }


    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k == 0){
            return new int[]{};
        }

        MaxQueue queue = new MaxQueue();
        for(int i = 0; i < k; i++){
            queue.push(nums[i]);
        }
        int[] res = new int[nums.length - k + 1];
        res[0] = queue.max();
        queue.pop(nums[0]);
        for(int i = k; i < nums.length; i++){
            queue.push(nums[i]);
            res[i - k + 1] = queue.max();
            queue.pop(nums[i - k + 1]);
        }

        return res;
    }

}