最大值减去最小值小于或等于num的子数组数量

给定数组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)的解法。

思路

有两个规律

  • 如果max(arr[i..j]) - min(arr[i..j]) <= num，那么ij往里缩，仍然满足要求
    因为范围缩小后，最大值只能比当前最大值小，而最小值只能比当前大，那么差值会变小，故仍满组要求

  • 如果max(arr[i..j]) - min(arr[i..j]) > num，不满足要求，那么ij往外扩大，仍不满足要求
    因为范围扩大，最大值可能比当前还大，最小值可能比当前值还小，那么差值会变大，仍不满足要求

利用双端队列，利用双端队列动态记录子数组的大小值

qmax和qmin是双端队列，记录大小值的序号，且满足数组的顺序是有序的
由于过程中ij一直只增不减，且到末尾就停止，相当于2n次遍历，
而更新qmax和qmin时，所有的数字都是进出各一次队列，相当2n次遍历
故一共4n次遍历，时间复杂度是o(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static int getNum(int[] arr, int num){
	if(arr == null || arr.length == 0){
		return 0;
	}
	LinkedList<Integer> qmax = new LinkedList<Integer>();
	LinkedList<Integer> qmin = new LinkedList<Integer>();
	int i = 0;
	int j = 0;
	int res = 0;
	while(i < arr.length){
		while(j < arr.length){
			//更新qmax,满足依次递减
			while(!qmax.isEmpty() && arr[j] >= arr[qmax.getLast()]){
				qmax.removeLast();
			}
			qmax.add(j);
			//更新qmin,满足依次递增
			while(!qmin.isEmpty() && arr[j] <= arr[qmin.getLast()]){
				qmin.removeLast();
			}
			qmin.add(j);
			//判断是否不符条件，如果不符，后面的都不会符合
			if(arr[qmax.getFirst()] - arr[qmin.getFirst()] <= num){
				//这里不能更新res，因为当i增加的时候j一直都是在最后，不会进入到此循环内，不能正确的计数
				//res ++;
			}else{
				break;
			}
			j++;
		}
		//更新窗口，因为i会变化，所以要将原来的pop
		if(qmax.getFirst() <= i){
			qmax.removeFirst();
		}
		if(qmin.getFirst() <= i){
			qmin.removeFirst();
		}
		//这里表示[i,i+1],[i,i+2],...,[i,j-1][i,j]都是符合条件的
		//一共是j-i组
		res += j-i;
		i++;
	}
	return res;
}