题解 | #最大值减去最小值小于或等于num的子数组数量

import java.util.Scanner;

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int num = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            System.out.println(getNum(arr, num));
        }
    }

    public static int getNum(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return 0; // 检查数组是否为空或长度为0
        }
        LinkedList<Integer> qmin = new LinkedList<>(); // 存储最小值的双端队列
        LinkedList<Integer> qmax = new LinkedList<>(); // 存储最大值的双端队列
        int i = 0; // 子数组的起始位置
        int j = 0; // 子数组的结束位置
        int res = 0; // 满足条件的子数组计数

        while (i < arr.length) { // 遍历数组
            while (j < arr.length) { // 扩展子数组的右边界
                //qmin 队列是一个单调递增队列，队列的最后一个元素（peekLast()）是队列中最近添加且最大的元素。
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                    qmin.pollLast(); // 更新最小值队列
                }
                qmin.addLast(j);
                //qmax 队列是一个单调递减队列，队列的最后一个元素（peekLast()）是队列中最近添加且最小的元素。
                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
                    qmax.pollLast(); // 更新最大值队列
                }
                qmax.addLast(j);
                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                    break; // 如果当前子数组不满足条件，则退出内层循环
                }
                j++; // 扩展右边界
            }
            if (qmin.peekFirst() == i) {
                qmin.pollFirst(); // 移除过期的最小值
            }
            if (qmax.peekFirst() == i) {
                qmax.pollFirst(); // 移除过期的最大值
            }
            res += j - i; // 对于每一个以 i 开始的位置，从 i 到 j-1 的所有子数组都满足条件
            i++; // 移动左边界
        }
        return res; // 返回满足条件的子数组总数
    }

}

这段 Java 代码实现了查找数组中最大值减去最小值小于或等于 num 的所有子数组的数量。下面是代码的逐行解释：

1. 检查数组有效性：如果输入的数组为空或长度为零，直接返回0。
2. 初始化两个双端队列：qmin 用于维护子数组的最小值，qmax 用于维护子数组的最大值。
3. 初始化变量：i 和 j 分别作为子数组的左右边界，res 用于统计满足条件的子数组数量。
4. 外层循环：通过变量 i 遍历数组，代表子数组的起始位置。
5. 内层循环：通过变量 j 扩展子数组的右边界。使用双端队列更新子数组的最大值和最小值。如果当前子数组的最大值和最小值的差大于 num，则停止内层循环。
6. 更新队列：如果队列头部元素是子数组的起始位置，则将其移除。
7. 计算子数组数量：将 j - i 加到 res 上，这表示以 i 为起始位置，有 j - i 个子数组满足条件。
8. 移动左边界：增加 i，以检查下一个可能的子数组。
9. 返回结果：所有满足条件的子数组数量。

通过这种方法，代码有效地计算了所有满足 "最大值减去最小值小于或等于 num" 条件的子数组数量。