算法

(双指针+单调队列) $\mathcal{O}(n)$

做法同 LC1438

C++ 代码

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int k, n;
    cin >> k >> n;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    deque<int> qMax, qMin;
    int l = 0, ans = 0;
    rep(r, n) {
        while (qMax.size() and qMax.back() < a[r]) {
            qMax.pop_back();
        }
        while (qMin.size() and qMin.back() > a[r]) {
            qMin.pop_back();
        }
        qMax.push_back(a[r]);
        qMin.push_back(a[r]);
        while (qMax.size() and qMin.size() and qMax.front() - qMin.front() > k) {
            if (qMin.front() == a[l]) {
                qMin.pop_front();
            }
            if (qMax.front() == a[l]) {
                qMax.pop_front();
            }
            l++;
        }
        ans = max(ans, r-l+1);
    }

    cout << ans << '\n';

    return 0;
}