//详情请见左神书籍，这个算法碉堡了
//我针对一些代码写些注释方便理解
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main()
{
	long long n; long long num;
	cin >> n >> num;
	vector<long long> datas(n, 0);
	for (int i = 0; i<n; i++)
	{
		long long x;
		cin >> x;
		datas[i] = x;
	}
        //以上用于输入
	deque<int> dq1;//最大值队列
	deque<int> dq2;//最小值队列
	int res = 0;
	int j = 0;
	int i = 0;
	for (; i<datas.size(); i++)
	{ //以i为起始位置的子数组
            for (; j<datas.size(); j++)
		{
			while (!dq1.empty() && datas[j] >= datas[dq1.back()])
				dq1.pop_back();
			dq1.push_back(j);
			while (!dq2.empty() && datas[j] <= datas[dq2.back()])
				dq2.pop_back();
			dq2.push_back(j);
                        //如果最大值减去最小值大于num就break，此时最大值
                        //减去最小值大于num一定是由于j的插入
			if (datas[dq1.front()] - datas[dq2.front()]>num)
				break;
		}
		if (dq1.front() == i)//如果队头是i位置的元素，i加一后就过期删掉
			dq1.pop_front();
		if (dq2.front() == i)
			dq2.pop_front();
		res += j - i;//以i为开头的小于num的子数组长度j-i
	}
	cout <<res <<endl;
}

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

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;
    }
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin>>n>>m;
    int a[n], cnt=n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0,j=1,l=0,r=0, Max, Min;i<n-1;i++){
        if(l<=i || r<=i){
            Max = Min = a[i];
            l = r = i;
            for(j=i+1;j<n;j++){
                if(a[j]>Max){
                    Max = a[j];
                    l = j;
                }
                if(a[j]<Min){
                    Min = a[j];
                    r = j;
                }
                if(Max-Min>m)
                    break;
            }
        }
        cnt += j-i-1;
    }
    cout<<cnt<<endl;
    return 0;
}

// golang 版本的，用 gods 库提供的双链表
import (    "fmt"  dll "github.com/emirpasic/gods/lists/doublylinkedlist" ) 




func getArrayNum(nums []int, k int) int {
	qMax := dll.New()
	qMin := dll.New()
	res := 0
	i, j := 0, 0
	for ; i < len(nums); i++ {
		for j < len(nums) {
			preMax, _ := qMax.Get(qMax.Size() - 1)
			for qMax.Size() > 0 && nums[preMax.(int)] <= nums[j] {
				qMax.Remove(qMax.Size() - 1)
				preMax, _ = qMax.Get(qMax.Size() - 1)
			}
			qMax.Append(j)
			preMin, _ := qMin.Get(qMin.Size() - 1)
			for qMin.Size() > 0 && nums[preMin.(int)] >= nums[j] {
				qMin.Remove(qMin.Size() - 1)
				preMin, _ = qMin.Get(qMin.Size() - 1)
			}
			qMin.Append(j)
			preMax, _ = qMax.Get(0)
			preMin, _ = qMin.Get(0)
			if nums[preMax.(int)]-nums[preMin.(int)] > k {
				break
			}
			j++
		}
		qq, _ := qMin.Get(0)
		mm, _ := qMax.Get(0)
		if qq.(int) == i {
			qMin.Remove(0)
		}
		if mm.(int) == i {
			qMax.Remove(0)
		}
		res += j - i
	}
	return res
}

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, num;
    scanf("%d%d", &n, &num);
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    
    deque<int> qmax, qmin;
    int res = 0;
    
    int i = 0, j = 0;
    
    qmax.push_back(0);
    qmin.push_back(0);
    
    while(i < n){
        while(j < n && v[qmax.front()] - v[qmin.front()] <= num){
            j++;
            while(!qmax.empty() && v[qmax.back()] < v[j])
                qmax.pop_back();
            qmax.push_back(j);
            
            while(!qmin.empty() && v[qmin.back()] > v[j])
                qmin.pop_back();
            qmin.push_back(j);
        }
        
        res += j - i;
        
        i++;
        
        if(qmax.front() < i)
            qmax.pop_front();
        
        if(qmin.front() < i)
            qmin.pop_front();
    }
    
    printf("%d\n", res);
    return 0;
} 

今天吃火龙果

let qmax=[],qmin=[]
let i=0,j=0
while(j<line.length&&i<line.length){ 
    // j一定是极值进栈才会i右移
    //如果极值进栈则先处理前面的 先不让极值进栈
    while(qmin.length>0&&qmax.length>0&&((line[j]<line[qmin[0]]&&line[qmax[0]]-line[j]>n)
    ||(line[j]>line[qmax[0]]&&line[j]-line[qmin[0]]>n))){
        res+=j-i
        if(qmin[0]==i)qmin.shift()      
        if(qmax[0]==i) qmax.shift()
        i++
    }
    while(qmin.length>0 && line[qmin[qmin.length-1]]>line[j]) qmin.pop()         
    qmin.push(j)
    while(qmax.length>0 && line[qmax[qmax.length-1]]<line[j]) qmax.pop()
    qmax.push(j)  
    j++

}

// j到最后一个了
while(qmin.length>0&&qmax.length>0&&line[qmax[0]]-line[qmin[0]]<=n){
    res+=j-i
    if(qmin[0]==i)qmin.shift()      
    if(qmax[0]==i)qmax.shift()
    i++
}

console.log(res)

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;
    }
}

C++抄书方法

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, num;
    cin>>n>>num;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    deque<int> dq_max;
    deque<int> dq_min;
    int i=0, j=0, res=0;
    while(i < n){
        while(j < n){
            if(dq_min.empty() || dq_min.back()!=j){
                while(dq_min.empty()==false && v[dq_min.back()]>v[j])
                    dq_min.pop_back();
                dq_min.push_back(j);
                while(dq_max.empty()==false && v[dq_max.back()]<v[j])
                    dq_max.pop_back();
                dq_max.push_back(j);
            }
            if(v[dq_max.front()] - v[dq_min.front()] > num)
                break;
            ++j;
        }
        res += j-i;
        if(dq_max.front() == i)
            dq_max.pop_front();
        if(dq_min.front() == i)
            dq_min.pop_front();
        ++i;
    }
    cout<<res;
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
/**
     * 利用两个双端队列来实现子数组最大值和最小值的更新
     */
    public static int getNum(int[] arr, int num) {
        // 排除三种特例：null 空数组[] num小于0
        if (arr == null || arr.length < 1 || num < 0) {
            return -1;
        }
        // 初始化子数组的最大值候选数组的下标
        LinkedList<Integer> qmax = new LinkedList<>();
        // 初始化子数组的最小值候选数字的下标
        LinkedList<Integer> qmin = new LinkedList<>();
        int res = 0;
        int i = 0;
        int j = 0;
        // 求以arr[i]开头的子数组中有多少个满足条件的
        while (i < arr.length) {
            while (j < arr.length) {
                // 更新j++后的最大值和最小值
                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
                    qmax.pollLast();
                }
                qmax.addLast(j);
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                    qmin.pollLast();
                }
                qmin.addLast(j);
                if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
                    // [i,j]不满足条件，则[i,j+1]...[i,arr.length-1]均不满足条件
                    break;
                }
                j++;
            }
            // [i,i]...[i,j-1]均满足条件，共有j-1-i+1个
            res += j - i;
            // 更新i++后的最大值和最小值
            if (qmax.peekFirst() == i) {
                qmax.pollFirst();
            }
            if (qmin.peekFirst() == i) {
                qmin.pollFirst();
            }
            i++;
        }
        return res;
    }

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