最大值减去最小值小于或等于num的子数组数量

自己实现的时候注意使用下标比较还是使用值在比较，不要搞混。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int num = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getArrayNum(arr, num);
        System.out.println(res);
    }

    //两个结论：1.到j不满足条件，a[i..j-1]满足条件所以a[m..n]都满足条件(i<=m<=n<=j-1)
    //2.a[i..j]不满足条件，则包含它的也都不满足条件(a[l..k],l<=i<=j<=k)
    //用a[i..j-1]代入条件：max(a[i..j])-min(a[i..j])<=num里进行归纳

    public static int getArrayNum(int[] arr, int num) {
        //判空
        if(arr == null || arr.length == 0){
            return 0;
        }
        //拿LinkedList作为双端队列来使用
        LinkedList qmax = new LinkedList();
        LinkedList qmin = new LinkedList();
        //j是不重置的，因为上面两个结论，到j不满足条件时，j是不变的，所以j只会不断地增长
        //j不重置则使用while语句
        int i = 0;
        int j = 0;
        int result = 0;
        //到j不满足条件时，i..j-1所有的子数组都满足条件，但是计数的时候只计算了从i开头的
        //后面剩下的会到它们为开头的时候计算（如i+1），这也是j不重置的原因
        while(i < arr.length){
            while(j < arr.length){
                //为了保证同一个下标只进栈一次，出栈一次，这样时间复杂度才能保证(每个元素O(1)，n个元素O(n))
                //如果break,j不变，而qmin.peekLast()正好是上一轮的j，后面i++，所以判断[i+1..j]是否满足条件
                //到j不满足条件，所以[i+1..j]不一定满足条件
                if(qmin.isEmpty() || qmin.peekLast() != j){
                    //双端队列结构
                    while(!qmax.isEmpty() && arr[j] >= arr[qmax.peekLast()]){
                        qmax.pollLast();
                    }
                    qmax.addLast(j);
                    while(!qmin.isEmpty() && arr[j] <= arr[qmin.peekLast()]){
                        qmin.pollLast();
                    }
                    qmin.addLast(j);
                }
                if(arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num){
                    break;
                }
                j++;
            }
            //以i开头一共j-i个，a[i..i]到a[i..j-1]
            result += (j - i);
            //开头i要自增，应该把队列中的i移除，只可能在最大和最小地方出现，要不就提前被弹出了
            if(qmax.peekFirst() == i){
                qmax.pollFirst();
            }
            if(qmin.peekFirst() == i){
                qmin.pollFirst();
            }
            i++;
        }
        return result;
    }
}

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        int n=sc.nextInt();
        int num=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        
        int[] min=new int[n];
        int[] max=new int[n];
        int minl=0;
        int minr=-1;
        int maxl=0;
        int maxr=-1;
        int i=0;
        int j=0;
        int res=0;
        while(i<n){
            while(j<n){ 
                while(minl<=minr&&arr[min[minr]]>=arr[j]) minr--;
                min[++minr]=j;
                while(maxl<=maxr&&arr[max[maxr]]<=arr[j]) maxr--;
                max[++maxr]=j;
                if(-arr[min[minl]]+arr[max[maxl]]>num){
                    break;
                }
                j++;
            }
            res+=j-i;
            if(max[maxl]==i) maxl++;
            if(min[minl]==i) minl++;
            i++;
        }
        System.out.println(res);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int num = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getArrayNum(arr, num);
        System.out.println(res);
    }
    
    public static int getArrayNum(int[] arr, int num) {
        if(arr == null || arr.length == 0)
            return 0;
        LinkedList<Integer> qmax = new LinkedList<>();
        LinkedList<Integer> qmin = new LinkedList<>();
        int res = 0;
        int L = 0;
        int R = 0;
        while(L < arr.length) {
            while(R < arr.length) {
                while(!qmax.isEmpty() && arr[qmax.getLast()] <= arr[R])
                    qmax.removeLast();
                qmax.add(R);
                while(!qmin.isEmpty() && arr[qmin.getLast()] >= arr[R])
                    qmin.removeLast();
                qmin.add(R);
                if(arr[qmax.getFirst()] - arr[qmin.getFirst()] > num)
                    break;
                R++;
            }
            res += R - L;
            if(qmax.getFirst() == L)
                qmax.removeFirst();
            if(qmin.getFirst() == L)
                qmin.removeFirst();
            L++;
        }
        return res;
    }
}