窗口：

窗口：

介绍窗口以及窗口内最大值或者最小值的更新结构（单调双向队列）

什么是窗口：

就是一个数组------有L和R指针，默认两个指针均位于数组的最左边即下标为 -1 的位置， 当有数字进入时R向右移动 当有数字删除时则L向右移动 且L 和R 不会回退且 L 不能到 R 右边~

思路： 双端队列（链表）：双端队列中既需要放置数据又需要放置位置下标，本质上存放下标就行，对应值从数组中就能获取。

可以从头 尾入 可以从尾 头出

规则： L< R 且 L,R 永远不回退~

分析逻辑为： 如果想实现窗口内最大值的更新结构： 使得双端队列保证从大到小的顺序

当放入元素时候 ：

​ （R增加） 头部始终存放的是当前最大的元素--- 如果即将进入双端队列的元素（因为 R 增加而从数组中取出放入双端队列中的元素）比上一个进入双端队列的元素小，则从尾部进入，新进入的元素直接连接在后面，否则 原来双端队列的尾部一直弹出（包含相等情况，因为晚过期） 直到为即将要放入的元素找到合适的位置，或者整个队列为空，然后放入新加入的元素。（见上面示例）

当窗口减数时候：

​ （L增加） ---L向右移---（index下标一定得保留）则需要检查当前头部元素index是否过期 若过期则需要从头部进行弹出

时间复杂度：因为从到到位滑过，每个数只会进队列一次，出队列一次，在队列中删除的数是不找回的，因此时间复杂度为：$$O(N)$$

具体应用：

生成窗口最大值数组：

题目

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右滑一个位置。

例如，数组为 [4,3,5,4,3,3,6,7]，窗口大小为 3 时候：

[4 3 5] 4 3 3 6 7 窗口中最大值为：5

4 [3 5 4] 3 3 6 7 窗口中最大值为：5

4 3 [5 4 3] 3 6 7 窗口中最大值为：5

4 3 5 [4 3 3] 6 7 窗口中最大值为：4

4 3 5 4 [3 3 6] 7 窗口中最大值为：6

4 3 5 4 3 [3 6 7] 窗口中最大值为：7

如果数组长度为 n，窗口大小为 w，则一共产生 n - w + 1 个窗口的最大值。

请实现一个函数：

输入：整型数组 arr，窗口大小为 w。

输出：一个长度为 n - w + 1 的数组 res，res[i]表示每一种窗口状态下的最大值。

上面的结果应该返回{5,5,5,4,6,7}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < k || nums.length == 0){
            return nums;
        }
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        for(int i = 0 ; i < nums.length; i++){
            while(!linkedList.isEmpty() && nums[linkedList.peekLast()] <= nums[i]){
                linkedList.pollLast();
            }
            linkedList.addLast(i);
            if(linkedList.peekFirst() == i - k){
                linkedList.pollFirst();
            }
            if(i >= k - 1){
                res[index++] = nums[linkedList.peekFirst()];
            }
        }
        return res;
    }
}