双端队列

#include<deque>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;

int main() {

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

        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
        }
        deque<int> qmax;
        deque<int> qmin;
        int i = 0;
        int j = 0;
        int res = 0;

        while (i < n) {
            while (j < n) {
                //这里可能有很多童鞋有疑问为什么qmax.back() != j
                //因为在上一次当中如果条件不满足就break了，但是j已经放进去了，所以是为了防止重新放置
                //这里换成qmax也可以；
                if (qmin.empty() || qmin.back() != j) {

                    //必须保证qmax的队头最大
                    while (!qmax.empty() && qmax.back() <= arr[j]) {
                        qmax.pop_back();
                    }
                    qmax.push_back(j);
                    //必须保证qmin的队头最小
                    while (!qmin.empty() && qmin.back() >= arr[j]) {
                        qmin.pop_back();
                    }
                    qmin.push_back(j);

                }
                //如果这里的j不满足后面的同样不满足，直接跳出循环尝试下一轮
                if (arr[qmax.front()] - arr[qmin.front()] > num) {
                    break;
                }
                j++;
            }
            res += j - i;
            //因为当前已经不能再用，所以如果qmax 和 qmin的front()为i则必须弹出
            if (qmax.front() == i) {
                qmax.pop_front();
            }
            if (qmin.front() == i) {
                qmin.pop_front();
            }
            i++;
        }
        cout << res << endl;
    }
    return 0;
}