给定数组arr和整数num，共返回有多少个子数组满足 <= num
数组长度N 时间复杂度O(N)
package TT;
import java.util.LinkedList;
public class Test127 {
public int getNum(int[] arr, int num){
if(arr==null || arr.length == 0){
return 0;
}
LinkedList<Integer> qmin = new LinkedList<Integer>();
LinkedList<Integer> qmax = new LinkedList<Integer>();
int i = 0;
int j = 0;
int res = 0;
while(i<arr.length){
while(j<arr.length){
while(!qmin.isEmpty() && arr[qmin.peekLast()]>=arr[j]){
qmin.pollLast();
}
qmin.addLast(j);
while(!qmax.isEmpty() && arr[qmax.peekLast()]<=arr[j]){
qmax.pollLast();
}
qmax.addLast(j);
if(arr[qmax.getFirst()]-arr[qmin.getFirst()]>num){
break;
}
j++;
}
if(qmin.peekFirst()==i){
qmin.pollFirst();
}
if(qmax.peekFirst()==i){
qmax.pollFirst();
}
res += j-i;
i++;
}
return res;
}
}
