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

生成两个双端队列 qMax 和 qMin ，分别维护窗口子数组的最大值和最小值更新的结构。

时间复杂度为 O(N) ，空间复杂度为 O(N) 。

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

/**
 * CD18
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int num = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            if (n == 0 || num < 0) {
                System.out.println(0);
            }
            LinkedList<Integer> qMin = new LinkedList<>();
            LinkedList<Integer> qMax = new LinkedList<>();
            int i = 0, j = 0, res = 0;
            while (i < n) {
                while (j < n) {
                    if (qMin.isEmpty() || qMin.peekLast() != j) {
                        while (!qMin.isEmpty() && arr[qMin.peekLast()] >= arr[j]) {
                            qMin.pollLast();
                        }
                        qMin.addLast(j);
                        while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[j]) {
                            qMax.pollLast();
                        }
                        qMax.addLast(j);
                    }
                    if (arr[qMax.getFirst()] - arr[qMin.getFirst()] > num) {
                        break;
                    }
                    j++;
                }
                res += j - i;
                if (qMin.peekFirst() == i) {
                    qMin.pollFirst();
                }
                if (qMax.peekFirst() == i) {
                    qMax.pollFirst();
                }
                i++;
            }
            System.out.println(res);
        }
    }
}