给定数组arr和整数num，返回共有多少个子数组满足如下情况：

max(arr[i..j]) - min(arr[i..j]) <= num

要求：O（N）实现。

 

思路：

         使用两个有序队列（相对于有序栈来命名）qmax和qmin，分别维护arr[i..j]的最大值和最小值更新结构。
         当子数组a[i..j]向右滑动一个位置变成arr[i..j+1]时，qmax和qmin可以在O（1）时间更新（上面已经分析，平均
         来看的确是O（1）），并且可以在O（1）时间得到arr[i..j+1]的最大值和最小值。
        步骤是这样的：i，j 从0开始，首先 j 向右滑动，这个过程中维护arr[i..j]的最大值和最小值更新结构，同时观察
        (max-min)的值，当其大于num时，停止 j，此时，arr[i..j] 内以 i 为起始满足条件的子数组有 j - i 个；
        然后 i 向右滑动一位，继续上诉过程，直到 i 到达数组末尾。

//若L~R满足条件  则在L~R之间 所有以L开头的子数组都满足条件
	public int getNum(int[] arr, int num) {
	    if (arr == null || arr.length == 0) {
	        return 0;
	    }
	    //qmax和qmin，分别维护arr[i..j]的最大值和最小值更新结构
	    LinkedList<Integer> qmax = new LinkedList<>();     //降序 头最大
	    LinkedList<Integer> qmin = new LinkedList<>();     //升序 头最小
	    int L = 0, R = 0;
	    int res = 0;
	    while (L < arr.length) {
	        while (R < arr.length) {
	        	//当前值大于等于队列尾  最大值结构更新
	            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
	                qmax.pollLast();
	            }
	            qmax.addLast(R);
	            //最小值结构更新
	            while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
	                qmin.pollLast();
	            }
	            qmin.addLast(R);
	            //不达标情况
	            if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
	                break;
	            }
	            R++;
	        }
	        //判断最大最小值过期了没
	        if (qmax.peekFirst() == L)
	            qmax.pollFirst();
	        if (qmin.peekFirst() == L)
	            qmin.peekFirst();
	        res += R - L;              //获得所有以L开头的子数组的数量
	        L++;                       //换一个开头
	    }
	    return res;
	}