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

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

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

• C++ 版

/*************************************************************************
	> File Name: 002.最大值和最小值差达标的子数组数量.cpp
	> Author: Maureen 
	> Created Time: 四 11/10 18:06:16 2022
 ************************************************************************/

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

//暴力对数器 O(n^3)
int right(vector<int> &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<int> &arr, int sum) {
    if (arr.size() == 0 || sum < 0) {
        return 0;
    }

    deque<int> qmax; //最大值的更新结构
    deque<int> qmin; //最小值的更新结构

    int n = arr.size();
    int count = 0;
    int r = 0;

    for (int l = 0; l < n; l++) { //枚举子数组的开始位置l
        while (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<int> generateRandomArray(int maxL, int maxV) {
    int len = rand() % (maxL + 1);
    vector<int> arr(len);
    for (int i = 0; i < len; i++) {
        arr[i] = (rand() % (maxV + 1)) - (rand() % (maxV + 1));
    }

    return arr;
}

void printArray(vector<int> &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<int> 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<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("测试结束");

	}
}