滑动窗口内的最大值
维护一个双端队列，存下标：
- 加数逻辑：当前数比队列尾部下标对应的值小，加在后面；大于等于：弹出尾部，直到小于尾部；
- 减数逻辑：判断当前队列头部是否与当前数下标一致，一致弹出，不一致保留。
例题
求一个数组内最大值减最小值小于等于num的所有子数组数量。
解：2个关键性质：
- 一个数组满足要求，则该数组的所有子数组满足
- 一个数组不满足要求，则该数组再往后扩仍不可能达标
public static int getNum(int arr[], int num){
if(arr == null || arr.length == 0)
return 0;
LinkedList<Integer> qmin = new LinkedList<>();
LinkedList<Integer> qmax = new LinkedList<>();
int L = 0;
int R = 0;
int res = 0;
while(L < arr.length){
while(R < arr.length){
while(!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R])
qmin.pollLast();
qmin.addLast(R);
while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R])
qmax.pollLast();
qmax.addLast(R);
if(arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) // 不满足条件，L左移
break;
R++;
}
if(qmin.peekFirst() == L)
qmin.pollFirst();
if(qmax.peekFirst() == L)
qmax.pollFirst();
res += R - L; // 以L开头的子数组
L++;
}
return res;
}
