题目

239. 滑动窗口最大值【困难】

题解

直接求每个滑动窗口内的最大值肯定可以，时间复杂度O(nk)，但是提交会超时，因此需要做一些优化

对于两个相邻的滑动窗口，他们共用k-1个元素，只有一个元素是变化的，根据这个特点进行优化

优先队列

初始时，将nums的前k个元素放入优先队列中。每当向右移动窗口时，就可以把一个新元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。如果堆顶元素不在滑动窗口中，则从堆中删除该元素。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n=nums.length;
        int[] res=new int[n-k+1];
        //优先队列
        PriorityQueue<int[]>queue=new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] pair1,int[] pair2){
                if(pair1[0]!=pair2[0])
                    return pair2[0]-pair1[0];//按照值的降序排序
                else
                    return pair2[1]-pair1[1];//如果值相等,按照下标的降序排序
            }
        });
        for(int i=0;i<k;i++){
            queue.offer(new int[]{nums[i],i});
        }
        res[0]=queue.peek()[0];//初始滑动窗口的最大值为堆顶
        for(int i=k;i<n;i++){
            queue.offer(new int[]{nums[i],i});
            
            //如果栈顶超出了滑动窗口,弹出
            while(queue.peek()[1]<i-k+1)
                queue.poll();
                
            //当前滑动窗口最大值进入结果数组
            res[i-k+1]=queue.peek()[0];
        }
        return res;
    }
}

时间复杂度：$O(nlogn)$，将一个元素放入堆的时间复杂度为O(logn)，最多共n个元素需要该操作

空间复杂度：$O(n)$，优先队列所使用的的空间

单调队列

是对方法一的继续优化，使用一个队列存储所有还没有被移除的下标。这些下标按从小到大的顺序存储，并且对应的nums值单调递减，即头部最大尾部最小。

1. 队尾元素（保证队尾元素大于新元素）：
当滑动窗口向右移动时，我们需要把一个新的元素放入队列中，不断将新的元素与队尾元素比较，如果前者>=后者，队尾元素可以被永久移除（因为最大值肯定不会是队尾元素），将其弹出队列。不断进行此操作，直到队列为空或者新的元素小于队尾的元素。

2. 队首元素（保证在窗口中）：
如果最大值在边界的最左侧，移动滑动窗口时还需要不断从队首弹出元素，直到队首元素在窗口中为止。

因为队首队尾都要弹出元素，因此需要使用双端队列。满足这种单调性的双端队列被称为单调队列。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n=nums.length;
        int[] res=new int[n-k+1];
        //单调队列
        Deque<Integer>queue=new LinkedList<>();
        for(int i=0;i<k;i++){
            //新的元素大于队尾，说明当前队尾一定不是最大值，可以出队
            while(!queue.isEmpty()&&nums[i]>=nums[queue.peekLast()])
                queue.pollLast();
            queue.addLast(i);
        }
        res[0]=nums[queue.peekFirst()];//初始滑动窗口的最大值为队头
        for(int i=k;i<n;i++){
            //消除不可能的队尾
            while(!queue.isEmpty()&&nums[i]>=nums[queue.peekLast()])
                queue.pollLast();

            //新元素下标入队
            queue.addLast(i);
            
            //如果队头超出了滑动窗口,弹出
            while(queue.peekFirst()<i-k+1)
                queue.pollFirst();
                
            //当前滑动窗口最大值（队头）进入结果数组
            res[i-k+1]=nums[queue.peekFirst()];
        }
        return res;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(k)$