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

import java.util.;
import java.io.;
public class Main{
public static int getNum(int []arr,int num){
if(arr==null||arr.length==0||num<0){
return 0;
}
LinkedList<integer> qmin= new LinkedList<integer>();
LinkedList<integer> qmax= new LinkedList<integer>();
int i=0;
int j=0;
int res=0;</integer></integer></integer></integer>

    while(i<arr.length){
        while(j<arr.length){

            //到j不满足条件，所以[i+1..j]不一定满足条件
            //保证qmin尾部为j位置
            if(qmin.isEmpty()||qmin.peekLast()!=j){
                //qmin尾部对应元素比arr[j]大，更换qmin
                //必须保证qmin队尾最小
                while(!qmin.isEmpty()&&arr[qmin.peekLast()]>=arr[j]){
                    qmin.pollLast();
                }
                qmin.addLast(j);
                //必须保证qmax的队尾最大
                while(!qmax.isEmpty()&&arr[qmax.peekLast()]<=arr[j]){
                    qmax.pollLast();
                }
                qmax.addLast(j);
            }
            //qmax的最小值 - qmin的最大值
            if(arr[qmax.getFirst()]-arr[qmin.getFirst()]>num){
                break;
            }
            j++;
        }
        res+=j-i;
        //开头i要自增，应该把队列中的i移除，只可能在最大和最小地方出现，要不就提前被弹出了
        if(qmin.peekFirst()==i){
            qmin.pollFirst();
        }
        if(qmax.peekFirst()==i){
            qmax.pollFirst();
        }
        i++;
    }

    return res;
//getNum结束    
}

public static void main(String[] args)throws IOException {
    BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
    int n,num;
    String[] line1 = in.readLine().split(" ");
    n=Integer.parseInt(line1[0]);
    num=Integer.parseInt(line1[1]);
    String[] arr = in.readLine().split(" ");
    int []data=new int[n];
    for(int i=0;i<n;i++){
        data[i]=Integer.parseInt(arr[i]);
    }

    int result =getNum(data,num);
    System.out.println(result);

}

}