目 录：
1、滑动窗口
2、滑动窗口的应用
2.1、生成窗口最大值数组2.2、求一个数组中最大值减去最小值小于或等于 num 的子数组数量（要求O(N)）
1、滑动窗口
生成窗口的最大值或者最小值数组，时间复杂度：O(N)。
可阅读：https://www.cnblogs.com/haozhengfei/p/a14049ec0869a8125a69f3af37471c77.html
普通解法的时间复杂度为O(N * win)，也就是每次对一个窗口遍历其中的 win 个数，选出最大值，最优解可以做到 O(N)。【分析】：
准备一个双端队列，双端队列存放着数组中的下标值。假设当前为 arr[i]，则放入规则如下：left 和 right 指针都只会向右移动，不会回退。
right 右滑，窗口加数：
1）如果 queue 为空，直接把下标 i 放入 queue 中；2）如果 queue 不为空，取出当前 queue 队尾存放的下标 j。如果 arr[j] > arr[i]，则直接把 i 放入队尾；3）如果 arr[j] <= arr[i]，则一直从 queue 的队尾弹出下标，直到某个下标在 queue 中的对应值大于 arr[i]，然后把 i 放入队尾 【为什么可以弹出，因为我永远比你晚过期，我又比你大或者和你一样大，有我在，你永远不可能最大，所以你可以滚了】left 右滑，窗口减数：
1）看弹出的 left 是否与队列头相等，如果相等，说明这个队列头已经不在窗口内了，所以弹出 queue 当前的队首元素 。双端队列的队头就是当前窗口最大值的下标。
public class Window {
private int[] arr;
private int left;
private int right;
private LinkedList<Integer> queue;
public Window(int[] arr){
this.arr = arr;
left = 0;
right = 0;
queue = new LinkedList<>();
}
// 往滑动窗口加数时对双端队列的操作
public void addNumToRight(){
if(right == arr.length){
// right已经到达最右了，滑动窗口无法再增加数了
return;
}
while(!queue.isEmpty() && arr[queue.peekLast()] <= arr[right]){
// 弹出比arr[right]小的数的下标
queue.pollLast();
}
queue.add(right);
right++;
}
// 移除双端队列最左边的值
public void removeNumFromLeft(){
if(left < right){
// 只有left小于right的时候，才有窗口存在
if(queue.peekFirst() == left){
// 要移除的这个数是双端队列的头，则弹出它，表示它已经不在窗口里，失效了
queue.pollFirst();
}
}
left++;
}
public Integer getMax(){
if(queue.isEmpty()){
return null;
}
// 双端队列的头结点就是当前滑动窗口的最大值
return arr[queue.peekFirst()];
}
}
2、滑动窗口的应用
上面的滑动窗口的实现是通用结构，即 left 和 righr 指针随便往右移，而在实际解题过程在，都是会限制窗口的大小。
2.1、生成窗口最大值数组
public class GetMaxNumInWindow {
public static int[] getMaxNumInWin(int[] arr, int win){
if(arr == null || arr.length < win || win < 1){
return null;
}
LinkedList<Integer> maxQueue = new LinkedList<>();
// 共有arr.length - win + 1个窗口，即共有arr.length - win + 1个最大值
int[] res = new int[arr.length - win + 1];
int index = 0;
for(int i = 0; i < arr.length; i++){
while(!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[i]){
/**
* 如果当前双端链表中的最后一个值比arr[i]小，则将其弹出，直到找到比arr[i]大的数，将arr[i]放在其后面，
* 如果maxQueue中没有比arr[i]大的数，那就将maxQueue中的数全部弹出，arr[i]放在头部
*/
maxQueue.pollLast();
}
maxQueue.addLast(i);
if(maxQueue.peekFirst() == i - win){
// 只有当窗口形成后才会有从双端队列头部失效一个数,即过期还是没过期
maxQueue.pollFirst();
}
if(i >= win - 1){
// 至少有一个窗口存在时，才有max
res[index] = arr[maxQueue.peekFirst()];
}
}
return res;
}
}
2.2、求一个数组中最大值减去最小值小于或等于 num 的子数组数量（要求O(N)）
【题目】 给定数组arr和整数num，共返回有多少个子数组满足如下情况:
max(arr[i..j]) - min(arr[i..j]) <= num
max(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表 示子数组arr[i..j]中的最小值。
【要求】 如果数组长度为N，请实现时间复杂度为O(N)的解法。
暴力方法是找出所有的子数组，再找每一个子数组的最大最小值看符合条件不，是O(N^3)。【分析】：这里有两个结论
如果子数组 arr[i..j] 满足条件，那么 arr[k..l]（i <= k <= l <= j）都满足条件，即若一个数组满足条件，它的所有子数组肯定满足条件。[max 变小 - min 变大 <= num 肯定成立]如果子数组 arr[i..j] 不满足条件，那么 arr[k..l] （k <= i，I >= j） 都不满足条件，即若一个数组不满足条件，所有包含它的数组肯定都不满足条件。【[max变大 - min变小 >= num肯定成立]【步骤】：准备两个双端队列，一个 maxQueue 是窗口内最大值更新结构，一个 minQueue 是窗口内最小值更新结构，left、right 表示窗口的左右边，窗口范围为 【left , right - 1】；算以 left 开头达标的子数组个数，每个 left 就可以算出一批答案，相加即可。
以 left 开头的情况下，right 往外扩，扩到不达标就停【因为再往外肯定也不达标】，算以 left 开头的子数组有多少个【这些子数组都达标的】；left 右移一位，然后重复 1）。
因为 left，right 都不后退，且每个数都只进出一次，所以时间复杂度是 O(N)。
public class GetAllLessNumSubArray {
public static int getAllSubArrayLessNum(int[] arr, int num){
if(arr == null || arr.length == 0){
return 0;
}
int left = 0;
int right = 0;
int res = 0;
LinkedList<Integer> maxQueue = new LinkedList<>(); // 最大值
LinkedList<Integer> minQueue = new LinkedList<>(); // 最小值
// 每个元素都会作为子数组中的第一个元素往外扩，进行尝试
while(left < arr.length){
// 尝试以left开头，right往外扩
while(right < arr.length){
// 更新最大值双端队列
while(!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[right]){
maxQueue.pollLast();
}
maxQueue.addLast(arr[right]);
// 更新最小值双端队列
while(!minQueue.isEmpty() && arr[minQueue.peekLast()] <= arr[right]){
minQueue.pollLast();
}
minQueue.addLast(arr[right]);
}
if(arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()] <= num){
right++; // right扩
}else{
break; // 不满足条件了，继续往外扩也是不满足的，left加1，right再重新从新left扩
}
res += right - left; // 以left开头的满足条件的子数组个数为：right - left 个
// left右移一位
if(left == maxQueue.peekFirst()){
maxQueue.pollFirst();
}
if(left == minQueue.peekFirst()){
minQueue.pollFirst();
}
left++;
}
return res;
}
}
