Q239滑动窗口最大值

思路

刚开始想的是你维护这个区间为有序的链表，每次向右移动一格，你只需要插入排序就可以，但是还需要记录你删除的元素，比如
3 4 2 1，k=3 一开始你维护的是 4 3 2，右移你需要删除3，你怎么找到呢，二分？就是排好序的确马上知道最大的就是第一个，但是你插入和删除的时候都需要查找

1 2 3 4 5，如果k=3,答案是3 4 5

其实队列里不需要把区间内的都存进去，比如走到4，4是目前最大的，则接下来的移动两次区间的最大值都不可能从4左边找，所以只需要保存4前面的2 3 不需要保存，

5 4 3 2 1，如果k = 3,这种都需要保存，因为你每次都舍弃最大的，需要接下来的倒数第二大保存,也就说，队列需要去除比新数小的所有数

比如下面的

5 2 3 1 4 7 如果k = 4,

队列的变化是
5
5 2
这个时候来了3，则需要把2去掉，保留3
5 3
5 3 1
此时是第一个窗口，最大值是队列第一个5，，同时因为需要右移删除的是5，所以队列5需要去掉，此时队列为 3 1
下一个是4，比3，1都大，队列变成
4
这个窗口最大值是4，这个时候也右移，但是删除的是2不是队列第一个4，所以不用管
下一个是7，此时队列变成7，最大值也是7

需要注意的点，为什么可以删除比新加数小的。

比如a1 a2 a3 a4 a5 窗口是 k =5 新的窗口变化是
第一次：a2 a3 a4 a5 a6, 加入了a6
第二次：a3 a4 a5 a6 a7
第三次：a4 a5 a6 a7 a8
第四次：a5 a6 a7 a8 a9
第五次：a6 a7 a8 a9 a10
第六次 a7 a8 a9 a10 a11

你会发现，如果a6是a2 a3 a4 a5 a6 中的最大值，后面的五次最大值都应该大于等于a6,因为他是最新加入的，所以他还可以保留一段时间。而a2 a3 a4 a5 即使在接下来的几次有保留也不会是最大值。

代码

class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k +1];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.getLast() < nums[i]){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }
        result[0] = deque.getFirst();
        for (int i = 0; i < nums.length - k; i++) {
          
            if (deque.getFirst() == nums[i]){
                deque.pollFirst();
            }
            while (!deque.isEmpty() && deque.getLast() < nums[i+k]){
                deque.pollLast();
            }
            deque.addLast(nums[i+k]);
             result[i+1] = deque.getFirst();
        }
        return result;
    }
}