1、思路

• 用滑动窗口最大值的思想，通过两个双端队列来分别维护一个最小单调栈和最大单调栈；

• i和j两个指针代表窗口的左右边界，若窗口内元素的最大值与最小值之差大于给定的num，则符合条件的子数组数量增加j - i，因为窗口内所有以num[i]为第一个元素的子数组肯定都是满足条件的，它们一共有j - i个。

2、代码

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int getNum(vector<int>& nums, int num)
{
    if (nums.empty()) return 0;

    deque<int> qmin, qmax;            //两个双端队列放数组元素的下标，分别用来模拟最小和最大单调栈
    int i = 0, j = 0, res = 0;

    while (i < nums.size())
    {
        while (j < nums.size())
        {
            //后一个条件是用来对应末尾的break的，如果触发break则j的值不会递增
            //避免了下一循环继续让同一个j进队列
            if (qmin.empty() || qmin.back() != j)
            {
                while (!qmin.empty() && nums[qmin.back()] >= nums[j])    //更新最小单调栈
                {
                    qmin.pop_back();    //队头放窗口内最小元素，队列从头到尾单调递增
                }
                qmin.push_back(j);

                while (!qmax.empty() && nums[qmax.back()] <= nums[j])    //更新最大单调栈
                {
                    qmax.pop_back();    //队头放窗口内最大元素，队列从头到尾单调递减
                }
                qmax.push_back(j);
            }

            if (nums[qmax.front()] - nums[qmin.front()] > num) break;    //已经往右扩展到极限了
            ++ j;
        }

        res += j - i;    //累加以nums[i]打头的子数组个数，即 j - i 个
        //下面 i 要往前移动一个位置，所以要判断队首元素是否为 i ，若是，则弹出
        if (qmin.front() == i) qmin.pop_front();
        if (qmax.front() == i) qmax.pop_front();
        ++ i;
    }

    return res;
}

int main()
{
    int n, num;
    cin >> n >> num;

    vector<int> nums(n);
    for (int i = 0; i < n; ++ i)
    {
        cin >> nums[i];
    }

    cout << getNum(nums, num) << endl;;

    return 0;
}