1、题目

给定一个整型数组 arr，和一个整数 num。

某个 arr 中的子数组 sub，如果想达标，必须满足：sub中最大值 - sub中最小值 <= num。

请返回 arr 中达标子数组的数量。

2、思路

结论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，如果达标就继续扩，一直到位置 ppp 不达标了，那么必须以 0 位置开始的子数组达标的数量一共有 p−0+1=p+1p - 0 + 1 = p + 1p−0+1=p+1 个。

然后 L 往右滑动到1，即 L = 1 时，R 继续往右扩，看是否达标，直到到达不能达标的位置，则能得到必须以 1 位置开始的子数组的达标数量。

注意：该过程中 L 和 R 都没有回退，一共只会滑过 n 个数，所以时间复杂度是 O(n)O(n)O(n)。

• C++ 版

/*************************************************************************> File Name: 002.最大值和最小值差达标的子数组数量.cpp> Author: Maureen > Created Time: 四 11/10 18:06:16 2022************************************************************************/#include 
#include 
#include 
using namespace std;//暴力对数器 O(n^3)
int right(vector &arr, int sum) {if (arr.size() == 0 || sum < 0) {return 0;}int n = arr.size();int count = 0;for (int l = 0; l < n; l++) {for (int r = l; r < n; r++) {int maxV = arr[l];int minV = arr[l];for (int i = l + 1; i <= r; i++) {maxV = max(maxV, arr[i]);minV = min(minV, arr[i]);}if (maxV - minV <= sum)count++;}}return count;
}//滑动窗口 O(n)
int way(vector &arr, int sum) {if (arr.size() == 0 || sum < 0) {return 0;}deque qmax; //最大值的更新结构deque qmin; //最小值的更新结构int n = arr.size();int count = 0;int r = 0;for (int l = 0; l < n; l++) { //枚举子数组的开始位置lwhile (r < n) {//最大值的更新while (!qmax.empty() && arr[qmax.back()] <= arr[r]) {qmax.pop_back();}qmax.push_back(r);//最小值的更新while (!qmin.empty() && arr[qmin.back()] >= arr[r]) {qmin.pop_back();}qmin.push_back(r);//该子数组是否达标if (arr[qmax.front()] - arr[qmin.front()] > sum) { //不达标break;} else {r++;}}count += r - l;//记录子数组达标的数量//检查队首元素是否过期if (qmax.front() == l) {qmax.pop_front();}if (qmin.front() == l) {qmin.pop_front();}}return count;
}vector generateRandomArray(int maxL, int maxV) {int len = rand() % (maxL + 1);vector arr(len);for (int i = 0; i < len; i++) {arr[i] = (rand() % (maxV + 1)) - (rand() % (maxV + 1));}return arr;
}void printArray(vector &arr) {if (arr.size()) {for (int i = 0; i < arr.size(); i++) {cout << arr[i] << " ";}cout << endl;}
} int main() {int maxL = 100;int maxV = 200;int testTime = 100000;cout << "Begin to test: " << endl;for (int i = 0; i < testTime; i++) {vector arr = generateRandomArray(maxL, maxV);int sum = rand() % (maxV + 1);int ans1 = right(arr, sum);int ans2 = way(arr, sum);if (ans1 != ans2) {cout << "Oops!" << endl;printArray(arr);cout << sum << endl;cout << ans1 << endl;cout << ans2 << endl;break;}if (i % 100 == 0) cout << i << " cases passed!" << endl;}cout << "Test end!" << endl;return 0;
}

• Java 版

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 maxWindow = new LinkedList<>();LinkedList 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 testpublic 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 testpublic 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("测试结束");}
}