最大值减去最小值小于等于num的子数组数量（单调队列）
问题重述：
给定数组 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 和 num，其中 n 表示数组 arr 的长度
第二行输入n个整数XiX_iXi，表示数组arr中的每个元素
输出描述:
输出给定数组中满足条件的子数组个数
示例1
输入
5 2
1 2 3 4 5
输出
12
问题分析：
这道题要求子数组中的最大值减去最小值小于等于num，那么我们的题目要求也就变成了求子数组的最大值和最小值，此外，当一个子数组满足要求时，这个子数组中的每一个子数组都满足条件。（因为这个子数组的最大值和最小值满足条件，该子数组的子数组最大值一定小于等于原来的最大值，最小值一定大于等于原来的最小值），我们可以固定子数组左边界，然后右边界向右扩张，每次扩张都进行条件判断，满足条件则继续扩张，不满足则停止向右扩张，记录子数组数量，左边界向右扩张一位，右边界继续扩张，直到不满足条件左边界再次向右扩张。直到遍历完整个数组。
解法：
单调队列
解题：
代码：
package cn.basic.algorithm;
import java.util.LinkedList;
import java.util.Scanner;
/**
* @author FOLDN
* 最大值减去最小值小于等于num的子数组数量
* 给定数组qrr和整数num，得到子数组数量
*/
public class NumArrayNumber {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int num = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(getArrayNumber(arr,num));
}
public static int getArrayNumber(int[] arr,int num){
if (arr == null || arr.length < 0 || num <0){
return 0;
}
// 生成一个最大队列和一个最小队列，分别用于记录单调最大和单调最小
LinkedList<Integer> maxQueue = new LinkedList<Integer>();
LinkedList<Integer> minQueue = new LinkedList<Integer>();
// 定义三个变量，i为数组左边元素，j为数组右边元素，res为最终子数组数量结果
int i = 0;
int j = 0;
int res = 0;
while (i < arr.length){
while (j < arr.length){
/*每一次循环完成后，当break时，此时的j其实已经加入了最大和最小队列，我们加这个条件就是为了避免重复判断，
使用minQueue和maxQueue是一样的，因为两个队列中的最后一个元素都是j，这样就可以达到O（n）的时间复杂度，但其实不加这个条件也不会非常影响时间*/
if (minQueue.isEmpty() || minQueue.peekLast() != j){
while(!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[j]){
// 当队列的最后一个元素对应的数组元素小于当前数组元素时，加入当前数组元素会破坏队列的单调性，所以弹出队列的最后一个元素
maxQueue.pollLast();
}
// 经过上述循环，此时加入数组元素不会影响队列的单调性
maxQueue.addLast(j);
while(!minQueue.isEmpty() && arr[minQueue.peekLast()] >= arr[j]){
// 当队列的最后一个元素对应的数组元素大于于当前数组元素时，加入当前数组元素会破坏队列的单调性，所以弹出队列的最后一个元素
minQueue.pollLast();
}
// 经过上述循环，此时加入数组元素不会影响队列的单调性
minQueue.addLast(j);
}
// 当添加完当前元素后，需要和题目条件进行对比，如果条件不满足，则结束循环，记录子数组数量
if ((arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()]) > num){
break;
}
j++;
}
res += (j-i);
/*此时应该数组左边向右扩张一位，但是扩张之后要考虑当前maxQueue和minQueue中的最大元素和最小元素是否还属于当前的数组，
也就是如果当前最大最小元素为被移除的那个元素，则要把这个元素从队列中删除*/
if (maxQueue.peekFirst() == i){
maxQueue.pollFirst();
}
if (minQueue.peekFirst() == i){
minQueue.pollFirst();
}
// 进行完条件判断后，将i更新
i++;
}
return res;
}
}
代码解析
这道题我们使用单调队列来解决，首先定义两个LinkedList，用来对最大值和最小值进行更新处理，使队列单调，队首为最大值和最小值，定义三个变量，子数组左右边界和满足条件的子数组数量。我们对子数组左右边界进行循环遍历，首先对两个单调队列进行更新处理，对当前要加入的数组元素进行判断，如果加入队列会影响队列的单调性，那么将队列的队尾元素弹出，直到当前元素加入不会影响队列单调性，加入当前元素到队列尾部（队列只能从队尾加入，删除队首和队尾都可以）。更新完两个队列后，进行条件判断，看当前的子数组是否满足最大值减去最小值小于等于num，如果满足条件，那么子数组右边界可以继续向右扩张，如果不能满足，则退出当前循环。退出循环后记录当前子数组的子数组数（由问题分析可知，该子数组的每一个子数组都满足题目条件），该数组的子数组数量为右边界减去左边界（此时的arr[i,i].....arr[i,j-1]都满足条件arr[i,j]不满足条件，所以数量为j-i），记录完子数组数量后，左边界向右扩张，需要注意的是，可能被我们排除的左边界此时是两个队列的队首元素，所以我们需要进行条件判断，如果为队首则弹出，左边界扩张。最后两个循环都完成后，返回子数组数量。此时我们对代码进行分析，发现代码不能达到O（n）的时间复杂度，因为在每一次向右扩张后和题目要求进行比较时，当条件不满足条件，退出循环时，当前的右边界下标其实已经加入了队列，当我们在进行下一次判断时会进行重复判断，所以我们在进行队列更新之前，进行一次条件判断，当前要加入的元素不等于队列最后一个元素，或者该队列为空，我们进行条件判断的队列可以是最大队列也可以是最小队列。
总结：
单调队列和单调栈的适用范围：
单调队列一般用于计算一个范围内的最大值或者最小值，单调栈一般用来计算当前元素左右的较大值或者较小值