什么是滑动窗口
首先题目给定的参数一般是一个数组
有两个指针，例如l指针和r指针，l指针和r指针的运动方向是相同的，并且l指针不能超过r指针
一个数从一边进来，从一边出去
维护窗口内最大值或最小值的更新结构，通常还需要一个双端队列
比如给定的数组是：[6,4,2,3,5,7,0,5]
定义一个双端队列deque，存储的是数组下标
窗口r指针往右划，比如滑到2，则6、4、2入队列
r指针再滑到3，先弹出2，3入队列，也就是保证队列里面从大到小排列（相等也弹出），不满足的数从尾部弹出
此时窗口的最大值就是双端队列的头部的数
如果l指针往右划，就把出窗口的数，从队列弹出，就可以维持窗口内最大值总是队列头部
这种做法的时间复杂度O(n)，因为每个数只进窗口一次，出窗口一次，比起暴力遍历要优化很多
1、故定大小的窗口从左往右划过数组，返回每个窗口中的最大值
固定大小的窗口从左往右划过数组arr，返回每个窗口中的最大值
窗口大小为w
/**
* 固定大小的窗口从左往右划过数组arr，返回每个窗口中的最大值
* 窗口大小为w
* Created by huangjunyi on 2022/9/4.
*/
public class Window01 {
public static int[] getMaxInWindow(int[] arr, int w) {
if (arr == null || arr.length < w || w <= 0) return null;
//用一个双端队列记录窗口内最大值的优先级，记录的时数组下标
Deque<Integer> deque = new LinkedList<>();
//结果数的计算公式 N - W + 1
int[] res = new int[arr.length - w + 1];
int index = 0;
for (int r = 0; r < arr.length; r++) {
//每次往队列里面压入元素时，保证从左往右递减的顺序
while (!deque.isEmpty() && arr[deque.peekLast()] <= arr[r]) deque.pollLast();
deque.addLast(r);
//如果判断到划出窗口的数的下标正好等于双端队列头部记录的下标，那边从双端队列弹出头部元素
//出窗口的数的下标 r - w
if (deque.peekFirst() == r - w) {
deque.pollFirst();
}
//保证窗口的左边界来到下标0（形成一个有效的窗口），才开始往结果集放入元素
if (r >= w - 1) {
res[index++] = arr[deque.peekFirst()];
}
}
return res;
}
}
2、给定一个整形数组arr，整数sum，如果arr中的子数组sub，如果想达标，必须满足：sub中最大值-sub中最小值 <= sum。返回arr中达标子数组的数量
给定一个整形数组arr，整数sum，
如果arr中的子数组sub，如果想达标，必须满足：
sub中最大值-sub中最小值 <= sum
返回arr中达标子数组的数量
这里达标子数组有两个特征：
1、 假设有一个达标的子数组，范围是从L到R，那么该子数组的子数组，都是达标的因为范围缩小，max-min只会更小不会更大；
2、 假设有一个子数组是不达标的，范围从L到R，那么该数组往左扩或者往右扩，都是不达标的因为范围扩大，max-min只会更大不会更小；
所以可以通过滑动窗口求解
左指针l不动，此时求以l为开头的子数组达标的数量
右指针r，不断往右扩，直到不达标，左指针l不动，此时达标子数组个数就是r-l
然后l指针往右划一位，把出窗口的数从双端队列吐出去（如果正好是出窗口的数）
周而复始，直到左指针l划过所有的数
/**
* 给定一个整形数组arr，整数sum，
* 如果arr中的子数组sub，如果想达标，必须满足：
* sub中最大值-sub中最小值 <= sum
* 返回arr中达标子数组的数量
* Created by huangjunyi on 2022/9/4.
*/
public class Window02 {
public static int process(int[] arr, int sum) {
if (arr == null || arr.length == 0) return 0;
Deque<Integer> minDeque = new LinkedList<>();
Deque<Integer> maxDeque = new LinkedList<>();
int res = 0;
int l = 0, r = 0;
while (l < arr.length) {
while (r < arr.length) {
//小跟堆记录当前窗口的最小值
while (!minDeque.isEmpty() && arr[minDeque.peekLast()] > arr[r]) minDeque.pollLast();
minDeque.addLast(arr[r]);
//大根堆记录当前窗口的最大值
while (!maxDeque.isEmpty() && arr[maxDeque.peekLast()] < arr[r]) maxDeque.pollLast();
maxDeque.addLast(arr[r]);
//如果最大值减去最小值超了，就退出当前循环，否则r指针继续往右括
if (sum < arr[maxDeque.peekFirst()] - arr[minDeque.peekFirst()]) break;
r++;
}
// r-l为当前循环得出的达标子数组的数量，累加到结果中取
res += (r - l);
/*
l指针往右推一位，继续下一轮循环
但l++前，要检查两个堆的堆顶是否是l指针指向的下标，是的话要删除
对于小顶堆，不存在值为l又不是堆顶的情况，因为不是堆顶代表后面有比它更小的数的下标，如果是这样，那么l在上面就已经弹出了
对于大顶堆，不存在值为l又不是堆顶的情况，因为不是堆顶代表后面有比它更大的数的下标，如果是这样，那么l在上面就已经弹出了
*/
if (l == minDeque.peekFirst()) minDeque.pollFirst();
if (l == maxDeque.peekFirst()) maxDeque.pollFirst();
l++;
}
return res;
}
}
3、给定一个有序数组，从左往右依次表示X轴上从左往右点的位置。给定一个正整数k，返回如果有一根长度为k的绳子，最多能盖住几个点。绳子的边缘点碰到X轴上的点，也算盖住
给定一个有序数组，从左往右依次表示X轴上从左往右点的位置
给定一个正整数k，返回如果有一根长度为k的绳子，最多能盖住几个点
绳子的边缘点碰到X轴上的点，也算盖住
/**
* 给定一个有序数组，从左往右依次表示X轴上从左往右点的位置
* 给定一个正整数k，返回如果有一根长度为k的绳子，最多能盖住几个点
* 绳子的边缘点碰到X轴上的点，也算盖住
* Created by huangjunyi on 2022/9/17.
*/
public class WindowProblem01 {
public static int maxPoint(int[] arr, int k) {
/*
利用窗口求解，
l指针每次走一步，走到数组结尾就停
r指针在每次循环中尝试往右括，括到 arr[r] - arr[l] > k，就停
然后尝试用 r - l 更新max变量
*/
int l = 0;
int r = 0;
int max = Integer.MIN_VALUE;
while (l < arr.length) {
while (r < arr.length && arr[r] - arr[l] <= k) r++;
max = Math.max(max, r - l);
l++;
}
return max;
}
}