解法：DP & 双指针

维护 $f(i)$ 表示前 $i$ 个元素的分割方案。转移时，枚举上一个子段的末尾在哪，有转移方程

$$
f(i) = \sum f(j)
$$

其中 $j$ 满足 $\max(a_{j + 1}, a_{j + 2}, \cdots, a_i) - \min(a_{j + 1}, a_{j + 2}, \cdots, a_i) \le k$

直接计算 DP 方程的复杂度为 $\mathcal{O}(n^2)$，还需要进一步观察合法的 $j$ 有什么特征。

注意到，如果某个子数组的极值之差小于等于 $k$，那么它的子数组的极值之差也小于等于 $k$。这是典型的双指针特征，因此合法的 $j$ 就是一段连续值，从某个值一直取到 $(i - 1)$。用双指针算出最小的合法 $j$，再用前缀和计算区间和即可。复杂度 $\mathcal{O}(n\log n)$，这里的 $\log n$ 主要是我们需要用数据结构（比如 multiset）动态维护滑动窗口里的最小值和最大值。

参考代码（c++）

class Solution {
public:
    int countPartitions(vector<int>& nums, int K) {
        int n = nums.size();

        const int MOD = 1e9 + 7;
        // f[i]：前 i 个元素的分割方案数
        // g[i]：f 的前缀和
        long long f[n + 1], g[n + 1];
        f[0] = g[0] = 1;

        // 用 multiset 记录滑动窗口里的数，方便求出最小值和最大值
        multiset<int> ms;
        // 枚举双指针的右端点 i，计算合法子段左端点的最小值 j
        for (int i = 1, j = 1; i <= n; i++) {
            ms.insert(nums[i - 1]);
            while (j < i && *prev(ms.end()) - *ms.begin() > K) {
                ms.erase(ms.find(nums[j - 1]));
                j++;
            }

            // j 是最小的左端点
            // 那么上一个子段最小的右端点就是 j - 1
            // 前缀和就得减去 j - 2 的值
            f[i] = (g[i - 1] - (j - 2 >= 0 ? g[j - 2] : 0) + MOD) % MOD;
            g[i] = (g[i - 1] + f[i]) % MOD;
        }
        return f[n];
    }
};