给定一个整型数组 arr，和一个整数 num。
某个 arr 中的子数组 sub，如果想达标，必须满足：sub中最大值 - sub中最小值 <= num。
请返回 arr 中达标子数组的数量。
结论1：如果
[L...R]范围上的max - min <= sum，则L...R范围上的所有子数组都是达标的。
解释：假设[L'...R']是[L...R]的子数组
∵[L...R]max - [L...R]min <= sum
∴[L'...R']max' <= [L...R]max，[L'...R']min >= [L...R]min
因此：[L'...R']max' - [L'...R']min <= sum，依然是达标的。
结论2：如果
[L...R]范围上的max - min > sum，那么无论L往左扩还是R往右扩，产生的新的子数组一定是不达标的。
思路：准备一个最大值更新结构qmax 和一个最小值更新结构 qmin，用于维护最大值和最小值。
假设窗口一开始为0，此时 L = 0，让 R 往右扩，每扩一次就更新 qmax 和 qmin，如果达标就继续扩，一直到位置
p
p
p 不达标了，那么必须以 0 位置开始的子数组达标的数量一共有
p
−
0
+
1
=
p
+
1
p - 0 + 1 = p + 1
p−0+1=p+1 个。
然后 L 往右滑动到1，即 L = 1 时，R 继续往右扩，看是否达标，直到到达不能达标的位置，则能得到必须以 1 位置开始的子数组的达标数量。
注意：该过程中 L 和 R 都没有回退，一共只会滑过 n 个数，所以时间复杂度是
O
(
n
)
O(n)
O(n)。
/*************************************************************************
> File Name: 002.最大值和最小值差达标的子数组数量.cpp
> Author: Maureen
> Created Time: 四 11/10 18:06:16 2022
************************************************************************/
#include public class AllLessNumSubArray {
// 暴力的对数器方法 O(N^3)，枚举所有子数组
public static int right(int[] arr, int sum) {
if (arr == null || arr.length == 0 || sum < 0) {
return 0;
}
int N = arr.length;
int count = 0;
for (int L = 0; L < N; L++) {
for (int R = L; R < N; R++) {
int max = arr[L];
int min = arr[L];
for (int i = L + 1; i <= R; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
if (max - min <= sum) {
count++;
}
}
}
return count;
}
//优化：O(N^3) -> O(N)
// 结论1：如果[L...R] 范围上的max - min <= sum，那么 L...R 范围的所有子数组都是达标的
// 原因：假设 L'...R'是L...R的子数组，因为[L...R]max - [L...R]min <= sum，那么[L'...R']的max'<= max，而[L'...R']的min' >= min，所以max'- min' <= sum，也是达标的
//结论2：如果[L...R] 范围上的max - min > sum，那么无论L往左扩还是R往右扩，产生的新的子数组一定是不达标的
//思路：个准备一个最大值和最小值的更新结构qmax和qmin，用于维护最大值和最小值
//假设窗口一开始为0，此时L = 0，让R往右扩，每扩一次就更新qmax和qmin，如果达标就继续扩，一直到p位置不达标了，那么必须以0开始的子数组达标的数量一共有p-0+1 = p+1个；
//然后L往右滑动到1，即L=1的时候，R继续往右扩，看是否达标，直到到达不能达标的位置，则能得到必须以1开始的子数组的达标数量；
//......
public static int num(int[] arr, int sum) {
if (arr == null || arr.length == 0 || sum < 0) {
return 0;
}
int N = arr.length;
int count = 0;
LinkedList<Integer> maxWindow = new LinkedList<>();
LinkedList<Integer> minWindow = new LinkedList<>();
int R = 0; //不回退
//L和R位置都不回退，一共只过N个数，所以时间复杂度是O(n)
for (int L = 0; L < N; L++) { //依次尝试窗口以0开始[0...、[1...、[2...的情况
//[L,R)，如果L=R，说明窗口内没数
while (R < N) { //[L...R，R往右扩，直到初次不达标停止
while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {
maxWindow.pollLast();
}
maxWindow.addLast(R);
while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {
minWindow.pollLast();
}
minWindow.addLast(R);
if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] > sum) {
break;
} else {
R++;
}
}
count += R - L;
//如果L过期，则滚蛋
if (maxWindow.peekFirst() == L) {
maxWindow.pollFirst();
}
if (minWindow.peekFirst() == L) {
minWindow.pollFirst();
}
}
return count;
}
// for test
public static int[] generateRandomArray(int maxLen, int maxValue) {
int len = (int) (Math.random() * (maxLen + 1));
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
}
return arr;
}
// for test
public static void printArray(int[] arr) {
if (arr != null) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int maxLen = 100;
int maxValue = 200;
int testTime = 100000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxLen, maxValue);
int sum = (int) (Math.random() * (maxValue + 1));
int ans1 = right(arr, sum);
int ans2 = num(arr, sum);
if (ans1 != ans2) {
System.out.println("Oops!");
printArray(arr);
System.out.println(sum);
System.out.println(ans1);
System.out.println(ans2);
break;
}
}
System.out.println("测试结束");
}
}