2025-11-25：统计极差最大为 K 的分割方式数。用go语言，给定一个整数数组 nums 和一个整数 k。

要求把 nums 划分成若干个相邻且非空的子数组（分段），使得每一段内元素的最大值与最小值之差不超过 k。

求符合条件的所有划分方案的数量。结果可能很大，请对 1000000007 取模后输出。

2 <= nums.length <= 50000。

1 <= nums[i] <= 1000000000。

0 <= k <= 1000000000。

输入： nums = [9,4,1,3,7], k = 4。

输出： 6。

解释：

共有 6 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 k = 4：

[[9], [4], [1], [3], [7]]

[[9], [4], [1], [3, 7]]

[[9], [4], [1, 3], [7]]

[[9], [4, 1], [3], [7]]

[[9], [4, 1], [3, 7]]

[[9], [4, 1, 3], [7]]

题目来自力扣3578。

程序运行步骤分解

1. 初始化

• 创建一个DP数组 f，其中 f[i] 表示数组前 i 个元素（即 nums[0] 到 nums[i-1]）的有效分割方案数量。初始时，f[0] 被设置为1，这表示一个空数组有一种分割方式（即不进行任何分割的基础情况）。

• 初始化两个空的单调队列 minQ 和 maxQ，分别用于维护当前窗口内的最小值和最大值的索引。这两个队列是保证高效计算极差的关键。

• 变量 sumF 用于记录当前滑动窗口内有效的DP值之和。变量 left 作为滑动窗口的左边界指针，初始为0。

2. 遍历数组并处理每个元素程序从左到右遍历数组，对于每个当前位置 i（对应元素 x = nums[i]），执行以下三个主要操作：

• A. 元素入队并维护单调队列

• 将 f[i] 的值加到 sumF 中。这相当于为后续计算积累以 i-1 位置结尾的分割方案数。

• 将当前索引 i 加入到单调队列中，并维护队列的单调性：

• minQ（递增队列）：从队尾开始，移除所有其对应元素值大于或等于当前元素 x 的索引。然后将 i 加入队尾。这确保了队头始终是当前窗口内最小值的索引。

• maxQ（递减队列）：从队尾开始，移除所有其对应元素值小于或等于当前元素 x 的索引。然后将 i 加入队尾。这确保了队头始终是当前窗口内最大值的索引。

• 这个过程保证了队列是单调的，且队首元素就是当前窗口的极值。

• B. 调整窗口左边界（出队）

• 计算当前窗口 [left, i] 的极差，即 nums[maxQ[0]] - nums[minQ[0]]。

• 如果该极差大于给定的 k，则意味着当前窗口不符合条件。需要不断将左边界 left 向右移动，以缩小窗口范围，直到极差小于等于 k。

• 在移动 left 时，从 sumF 中减去 f[left]，因为以 left 为结尾的分割方案不再适用于新的窗口。

• 同时，检查两个单调队列的队首索引是否已经小于新的 left。如果是，则将该队首出队，因为它已经不在当前窗口内了。

• 此步骤确保了窗口 [left, i] 是满足极差条件的、以 i 为右端点的最长子数组。

• C. 更新动态规划数组

• 在确保了窗口 [left, i] 的有效性后，当前的 sumF 就代表了所有能够有效分割到当前位置 i 的方案总数。

• 因此，将 f[i+1] 更新为 sumF % mod。这表示，所有能够有效分割到 i 的方案，都可以通过在其末尾添加一个以 i 结尾的合法子段来形成一种新的分割方案。

3. 返回结果

• 当遍历完整个数组后，DP数组 f 的最后一个元素 f[n] 就是整个数组 nums 的有效分割方案总数，将其返回即可。

⏱️ 复杂度分析

• 总的时间复杂度：O(n)。整个算法只对数组进行了一次遍历。虽然内部有循环，但每个元素最多被压入和弹出单调队列各一次，因此所有操作的平均时间复杂度是常数级别的。所以，总时间复杂度是线性的 O(n)。

• 总的额外空间复杂度：O(n)。主要的空间开销来自于DP数组 f（大小为 n+1）以及两个单调队列 minQ 和 maxQ（最坏情况下各需要 O(n) 空间）。因此，总的空间复杂度是 O(n)。

Go完整代码如下：

package mainimport (    "fmt")func countPartitions(nums []int, k int) int {    const mod = 1_000_000_007    n := len(nums)    var minQ, maxQ []int    f := make([]int, n+1)    f[0] = 1    sumF := 0 // 窗口中的 f[i] 之和    left := 0    for i, x := range nums {        // 1. 入        sumF += f[i]        for len(minQ) > 0 && x <= nums[minQ[len(minQ)-1]] {            minQ = minQ[:len(minQ)-1]        }        minQ = append(minQ, i)        for len(maxQ) > 0 && x >= nums[maxQ[len(maxQ)-1]] {            maxQ = maxQ[:len(maxQ)-1]        }        maxQ = append(maxQ, i)        // 2. 出        for nums[maxQ[0]]-nums[minQ[0]] > k {            sumF -= f[left]            left++            if minQ[0] < left {                minQ = minQ[1:]            }            if maxQ[0] < left {                maxQ = maxQ[1:]            }        }        // 3. 更新答案        f[i+1] = sumF % mod    }    return f[n]}func main() {    nums := []int{9, 4, 1, 3, 7}    k := 4    result := countPartitions(nums, k)    fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-from collections import dequedef countPartitions(nums, k):    mod = 1_000_000_007    n = len(nums)    min_q = deque()    max_q = deque()    f = [0] * (n + 1)    f[0] = 1    sum_f = 0  # 窗口中的 f[i] 之和    left = 0    for i, x in enumerate(nums):        # 1. 入        sum_f = (sum_f + f[i]) % mod        # 维护最小值的单调队列        while min_q and x <= nums[min_q[-1]]:            min_q.pop()        min_q.append(i)        # 维护最大值的单调队列        while max_q and x >= nums[max_q[-1]]:            max_q.pop()        max_q.append(i)        # 2. 出        while nums[max_q[0]] - nums[min_q[0]] > k:            sum_f = (sum_f - f[left]) % mod            left += 1            if min_q[0] < left:                min_q.popleft()            if max_q[0] < left:                max_q.popleft()        # 3. 更新答案        f[i + 1] = sum_f % mod    return f[n]def main():    nums = [9, 4, 1, 3, 7]    k = 4    result = countPartitions(nums, k)    print(result)if __name__ == "__main__":    main()

C++完整代码如下：

#include <iostream>#include <vector>#include <deque>using namespace std;class Solution {public:    int countPartitions(vector<int>& nums, int k) {        const int mod = 1'000'000'007;        int n = nums.size();        deque<int> minQ, maxQ;        vector<int> f(n + 1, 0);        f[0] = 1;        long long sumF = 0; // 窗口中的 f[i] 之和        int left = 0;        for (int i = 0; i < n; i++) {            int x = nums[i];            // 1. 入            sumF = (sumF + f[i]) % mod;            // 维护最小值的单调队列            while (!minQ.empty() && x <= nums[minQ.back()]) {                minQ.pop_back();            }            minQ.push_back(i);            // 维护最大值的单调队列            while (!maxQ.empty() && x >= nums[maxQ.back()]) {                maxQ.pop_back();            }            maxQ.push_back(i);            // 2. 出            while (nums[maxQ.front()] - nums[minQ.front()] > k) {                sumF = (sumF - f[left] + mod) % mod;                left++;                if (minQ.front() < left) {                    minQ.pop_front();                }                if (maxQ.front() < left) {                    maxQ.pop_front();                }            }            // 3. 更新答案            f[i + 1] = sumF % mod;        }        return f[n];    }};int main() {    vector<int> nums = {9, 4, 1, 3, 7};    int k = 4;    Solution solution;    int result = solution.countPartitions(nums, k);    cout << result << endl;    return 0;}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。

欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。