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

福大大架构师每日一题

发布于 2025-12-19 09:20:08

440

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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 main

import (
    "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 deque

def 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;
}