窗口：是一种运动轨迹，一种运动策略
L，R：可以选择让L往右，或让R往右，但L不能越过R
3,2,1,5,6,5,6,7,2,3,7
0 1 2 3 4 5 6 7 8 9 10
L
R R R R
3 2 1 5
L
2 1 5
R
你可以根据你自己的策略让L或R往右动，但是不要违反L<=R
每一次做出选择，窗口都有一个数的状况，你怎么样能够做到任务一个状态下都能方便的得到最大值
你可以遍历，但是时间复杂度是O（N）
下面来看一下如何获得窗口的最大值和最小值：
3 2 1 5 6 5 6 7 2 2 7
0 1 2 3 4 5 6 7 8 9 10
用双端队列，队列放的是位置
如果是最大值，要保证位置所代表的值从左往右是严格减少
R往右动时，双端队列更新的过程
R
0 1 2
3 2 1
3
5
4 5
6 5
6
6
7 8
7 2
7 9
7 2
10
7
L
L 往右动时，检查队列头部是否是一个过期位置，如果则pop
这个流程的实质是什么？
这个双端队列代表：如果此时的窗口在L依次往右滑时，哪些位置会依次成为最大值
eg:
给定一个数组[3,2,1,5,6,5,6,7,2,3,7] w=3,统计每个窗口的最大值 n=11,w=3
3
queue
入队要严格单调递减
3 2 1 0 6 5 6 7 2 3 7
0 1 2 3 4 5 6 7 8 9 10
存储下标，信息更多
arr v: 3 2 1 0
queue i: 0 1 2 3
入队规则：
1、i 位置入队：如果队列不空，且arr[i]>=arr[queue.peekLast] .>>>> queue.poll
queue.addLast(i);
2、 如果队列位置过期出队
queue.peekFist==i-w 出队
3、 什么时候统计结果？窗口形成时：i>=w-1
结果集 int[] result=new int[11-3+1] n-w+1
当 i-w+1>=0 统计结果 result[index++]=arr[queue.peekFirst]
public static int[] getMaxWindow(int[] arr,int w){
//先排除无效参数
if(arr==null||w<1||arr.length<w){
return null;
}
//准备一个双队列，这里放的是位置
LinkedList<Integer> queueMax=new LinkedList<>();
//收集的结果 n=8,w=3 res.length=8-3+1
int[] res=new int[arr.length-w+1];
int index=0;
//i->R
//每一个i位置代表当前让i位置上面所代表的值进窗口，这个i就是R，让R往右动
for(int i=0;i<arr.length;i++){
//这时是R往右动时的策略
//如果队列不为空且peekLast小于i位置的值，则出队
while (!queueMax.isEmpty() && arr[queueMax.peekLast()]<=arr[i]){
queueMax.pollLast();
}
//加入当前节点
queueMax.addLast(i);
//因为窗口大小是W，要维持窗口大小，所以i-w是过期的位置
//eg: i=3,w=3,则过期位置是0，把0位置弹出
//在一开始窗口还没有形成之前，是不会过期的
// 一直是判断队列左边位置是否已过期
if(arr[queueMax.peekFirst()]==i-w){
queueMax.pollFirst();
}
//窗口形成好之后，收集结果 i=2,w=3,此时就一个有效的形成好的窗口，则i+1==w
if(i>=w-1){
res[index++]=arr[queueMax.peekFirst()];
}
}
return res;
}
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
LinkedList<Integer> queue=new LinkedList<>();
int[] res=new int[nums.length-k+1];
int index=0;
for(int i=0;i<nums.length;i++){
while(!queue.isEmpty()&& nums[queue.peekLast()]<=nums[i]){//双端队列里面放的是位置
queue.pollLast();//弹出是poll
}
//queue放的是位置
queue.add(i);
//i=3,w=3 0
//检查队头的位置是不是过期位置，如果是，则弹出
if(queue.peekFirst()==i-k){
queue.pollFirst();
}
//在窗口形成之后，收集结果，i=2,k=3,i+1==w
if(i>=k-1){
res[index++]=nums[queue.peekFirst()];
}
}
return res;
}
}