给定数组arr和整数num， 共返回有多少个子数组满足如下情况：
max(arr[i..j]) - min(arr[i..j]) <= num
max(arr[i..j])表示子数组arr[i..j]中的最大值， min(arr[i..j])表示子数组arr[i.中的最小值。
【要求】
如果数组长度为N， 请实现时间复杂度为O(N)的解法。
子数组要求其中的元素是连续的
解法一：暴力法 O(N³) 不可取
通过循环，找遍数组中所有的子数组，同时判断子数组中的值是否满足条件，如果满足，则加入到结果中
解法二：
①、如果一个子数组从L->R中，arr[max] - arr[min] <= num，那么在L->R范围内的子数组都符合要求
②、如果一个子数组从L->R中，arr[max] - arr[min] > num，那么以L->R为基础向外扩的子数组都不符合要求
做两个双端队列，一个是窗口内最大值，另外一个是窗口内最小值
1）、开始时L在数组最左端 0 位置，R从最左端开始向右扩，直到再扩充一个值就不符合要求时，R停止，设此时为 x 位置
则以0位置开始的子数组有 x + 1个（0,0~1,……0~x） 这些子数组是以0为起始位置符合要求的所有子数组个数
2）、L向右边移动一个位置，更新两个窗口内的结构，然后R试着继续向右扩，重复上面的，然后就能得到以1为起始位置符合要求的所有子数组个数
L每次向右移动一个位置，R就开始向右扩
/**
* Created by Skye on 2018/5/3.
* 给定数组arr和整数num， 共返回有多少个子数组满足如下情况：
max(arr[i..j]) - min(arr[i..j]) <= num
max(arr[i..j])表示子数组arr[i..j]中的最大值， min(arr[i..j])表示子数组arr[i.中的最小值。
【要求】
如果数组长度为N， 请实现时间复杂度为O(N)的解法。
从当前位置 i 开始 采用双重循环， j 向后面开始扩充，采用两个队列，分别记录当前 i - j 的最大值和最小值
当 arrays[maxList.peekLast()] - arrays[minList.peekLast()] > num 时不满足题意，
则 j 停止扩充，然后计算从 i 到 j 共有多少个子数组 j - i 记录，
并且判断当前位置 i 是否还在最大或最小队列中，如果存在，则弹出，因为 i 马上要过期了
然后 i++ 继续扩充
*/
public class AllLessNumSubArray {
public static int lessNumArray(int[] arrays, int num){
if(arrays == null || arrays.length == 0) return 0;
LinkedList<Integer> maxList = new LinkedList<>();
LinkedList<Integer> minList = new LinkedList<>();
int res = 0;
int i = 0;
int j = 0;
while(i < arrays.length){
while(j < arrays.length){
while(!maxList.isEmpty() && arrays[maxList.peekLast()] <= arrays[j]){
maxList.pollLast();
}
while(!minList.isEmpty() && arrays[minList.peekLast()] >= arrays[j]){
minList.pollLast();
}
maxList.addLast(arrays[j]);
minList.addLast(arrays[j]);
j++;
if(arrays[maxList.peekLast()] - arrays[minList.peekLast()] > num){
break;
}
}
//判断是否超过了边值条件
if(maxList.peekFirst() == i) maxList.pollFirst();
if(minList.peekFirst() == i) minList.pollFirst();
res += j - i;
i++;
}
return res;
}
}