• 我们还可以进一步优化空间复杂度
• 将 $p[]$ 和前缀和数组 $f[]$，放到双指针里一起计算

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

using i64 = long long;
using pii = pair<int, int>;
const int P = 1000000007;

int solve(vector<int>& a, int n, int k) {
    vector<int> dp(n + 1, 0);  // dp(i): 前 i 个数的方案数
    dp[0] = 1;
    set<pii> s;
    int tmp = dp[0];  // 双指针之间的 dp 的和
    for (int i = 1, p = 1; i <= n; i++) {
        s.insert({a[i], i});
        // a[p] 到 a[i] 是已经插入的数
        while (s.rbegin()->first - s.begin()->first > k) {
            s.erase({a[p], p});
            tmp = (tmp - dp[p - 1] + P) % P;
            p++;
        }
        dp[i] = tmp;
        tmp = (tmp + dp[i]) % P;  // 右指针往右移
        // cout << "i= " << i << ", dp[i]= " << dp[i] << ", tmp= " << tmp << '\n';
    }
    return dp[n];
}

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(a, n, k) << '\n';

    return 0;
}

• 我们考虑优化下面 $O(n^2)$ 的转移过程
• 设 $p[i]$：表示 最小 的下标，使得 $a[p[i]], a[p[i]+1], \cdots, a[i]$ 是合法的子段
  • 如果我们能快速计算出 $p[]$，这个题就解决了
  • 注意到 $p[]$ 是 单调的（思考下为什么？），双指针登场
  • 利用双指针计算 $p[]$ 需要用 $set$ 维护双指针之间的值，所以最后的时间复杂度是 $O(nlog(n))$
  • 当然，还可以用 单调队列 计算 $p[]$，时间复杂度可以优化到 $O(n)$

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

using i64 = long long;
using pii = pair<int, int>;
const int P = 1000000007;

int solve(vector<int>& a, int n, int k) {
    // p(i)：表示 最小 的下标，使得 [a(p(i)), a(p(i)+1), ..., a(i)] 是合法的子段
    // 那么必然有 p[i] <= p[i + 1], 即 p[] 是单调的   
    vector<int> p(n + 1);   p[1] = 1;

    set<pii> s;  s.insert({a[1], 1});
    for (int i = 2; i <= n; i++) {
        p[i] = p[i - 1];
        s.insert({a[i], i});

        // 如果 s 中的 最大值 - 最小值 > k, 就要不断扩大 p[i]
        while (s.rbegin()->first - s.begin()->first > k) {
            s.erase({a[p[i]], p[i]});
            p[i]++;
        }
    }

    // dp(i): 前 i 个数的方案数, f 是 dp 的前缀和
    vector<int> dp(n + 1, 0);  dp[0] = 1;
    vector<int> f(n + 1, 0);   f[0] = 1;
    for (int i = 1; i <= n; i++) {
        int l = p[i];
        
        // dp[i] = sum(dp[l - 1], dp[l], ..., dp[i - 1]);
        // dp[i] = f[i - 1] - f[l - 2];
        dp[i] = f[i - 1] - (l - 2 >= 0 ? f[l - 2] : 0);
        dp[i] = (dp[i] + P) % P;
        f[i] = (f[i - 1] + dp[i]) % P;
    }

    return dp[n];
}

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(a, n, k) << '\n';

    return 0;
}

• $dp(i)$：前 $i$ 个数的方案数
• 计算 $dp(i)$ 时，考虑枚举包含 $a[i]$ 的子段
  • 比如 $a[j], a[j + 1], \cdots, a[i]$ 是合法的子段
  • 那么 $dp[i]$ 就应该加上 $dp[j - 1]$
• 状态 $O(n)$，转移 $O(n)$，所以时间复杂度是 $O(n^2)$，会 TLE

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

using i64 = long long;
using pii = pair<int, int>;
const int P = 1000000007;

int solve(vector<int>& a, int n, int k) {
    vector<int> dp(n + 1, 0);  // dp(i): 前 i 个数的方案数
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        int l = i, maxi = a[l], mini = a[l];
        while (l > 1) {
            int x = max(maxi, a[l - 1]);
            int y = min(mini, a[l - 1]);
            if (x - y <= k) {
                l--;
                maxi = x, mini = y;
            }
            else break;
        }
        for (int j = l - 1; j < i; j++) dp[i] = (dp[i] + dp[j]) % P;
    }
    return dp[n];
}

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(a, n, k) << '\n';

    return 0;
}