【题目】 给定数组 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,请实现时间复杂度为 O(N)的解法。
import java.util.LinkedList;
/**
* Created by 糖糖 on 2017/8/2.
*/
public class getnum33 {
public static int getnum(
int arr[],
int num){
LinkedList<Integer> qmin=
new LinkedList<>();
LinkedList<Integer> qmax=
new LinkedList<>();
int res=
0;
int i=
0;
int j=
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.peekFirst()]-arr[qmin.peekFirst()]>num)
break;
j++;
}
if(i==qmin.peekFirst())
qmin.pollFirst();
if(i==qmax.peekFirst())
qmax.pollFirst();
res+=j-i;
i++;
}
return res;
}
public static void main(String args[]){
int arr[]={
3,
4,
5,
1,
7,
8};
System.
out.print(
getnum(arr,
2));
}
}
