1、前言

2、思路

这道题刚开始是想使用一个最大堆来做，堆能很快求出最大的值，但是当窗口滑动时，需要将原来窗口左端的值去除。那么对于堆来说，需要遍历查找，而且还会经过一轮调整，所以会超出时间限制。

在这里我们可以使用单调队列的思路，单调队列意味着放入队列中的值都是单调递增或者递减（跟单调栈思路一样）。首先我们定义一个单调队列 monotonic，它有 push、pop、max 方法。push 主要压入当前值，pop 主要弹出滑动窗口最左端的值，max 可以获取当前滑动窗口最大值。

在 push 时，我们将使用单调栈的思路，如果队列非空且当前值大于队尾的值（从队尾开始淘汰，那么最终会使得单调队列队首最大），则淘汰队尾的值，直到跳出循环，然后将数字链接到队尾。

在 pop 时，pop 的是滑动窗口最左端的值，那么因为上述的 push 操作有剔除数的操作，所以此时要判断一下，最左端是否是否是队首的元素（即最大值），是则删除。

3、代码

public class Q239_MaxSlidingWindow {

    /**
     * 超时了
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if(nums == null || nums.length == 0 || nums.length < k){
            return new int[]{};
        }

        PriorityQueue<Integer> maxQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });


        for(int i = 0; i < k; i++){
            maxQueue.add(nums[i]);
        }

        int[] res = new int[nums.length - k + 1];
        res[0] = maxQueue.peek();
        for(int i = k, j = 1; i < nums.length; i++, j++){
            maxQueue.remove(nums[j - 1]);
            maxQueue.add(nums[i]);
            res[j] = maxQueue.peek();
        }

        return res;
    }

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

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

        public void pop(int n){
            // pop 都是取出队首的值，即滑动窗口中的值。
            // 因为之前都有清空的动作，所以 pop 的时候要判断一下
            if(n == queue.peekFirst()){
                queue.removeFirst();
            }
        }

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

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

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

            queue.push(nums[i]);
            // i - k + 1 是 res 数组的索引，也是滑动窗口的左端
            res[i - k + 1] = queue.max();
            queue.pop(nums[i - k + 1]);
        }

        return res;
    }

    public static void main(String[] args) {
        int[] res = new Q239_MaxSlidingWindow().maxSlidingWindow(new int[]{7, 2, 4}, 2);
        for (int re : res) {
            System.out.println(re);
        }
    }
}