划分型 DP + 单调队列优化（Python/Java/C++/Go）

2025年6月8日 12:15

O(n^2) 做法

本题是标准的划分型 DP，见 DP 题单的「§5.2 最优划分」。

一般定义 $f[i+1]$ 表示前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 在题目约束下，分割出的最少（最多）子数组个数，本题是定义成分割方案数。这里 $i+1$ 是为了把 $f[0]$ 当作初始值。

枚举最后一个子数组的左端点 $j$，那么问题变成前缀 $\textit{nums}[0]$ 到 $\textit{nums}[j-1]$ 在题目约束下的分割方案数，即 $f[j]$。

当子数组右端点 $i$ 固定时，由于子数组越长，最大值越大，最小值越小，最大最小的差值越可能大于 $k$。所以符合要求的左端点 $j$ 一定在一个连续区间 $[L,i]$ 中。累加 $f[j]$ 得

$$
f[i+1] = \sum_{j=L}^{i} f[j]
$$

初始值 $f[0] = 1$，空子数组算一个方案。也可以从递归的角度理解，递归到空子数组，就表示我们找到了一个合法分割方案。

答案为 $f[n]$。

O(n) 做法

由于 $i$ 越大，$L$ 也越大，可以用滑动窗口【基础算法精讲 03】。

同时，我们需要计算 239. 滑动窗口最大值和滑动窗口最小值，这可以用单调队列【基础算法精讲 27】解决。

维护窗口中的 $\displaystyle\sum_{j=L}^{i} f[j]$，记作 $\textit{sumF}$，转移方程优化成

$$
f[i+1] = \textit{sumF}
$$

注意取模。关于模运算的知识点，见模运算的世界：当加减乘除遇上取模。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        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 += f[i]

            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 -= f[left]
                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]

###java

class Solution {
    public int countPartitions(int[] nums, int k) {
        final int MOD = 1_000_000_007;
        int n = nums.length;
        Deque<Integer> minQ = new ArrayDeque<>(); // 更快的写法见【Java 数组】
        Deque<Integer> maxQ = new ArrayDeque<>();
        int[] f = new int[n + 1];
        f[0] = 1;
        long sumF = 0; // 窗口中的 f[i] 之和
        int left = 0;

        for (int i = 0; i < n; i++) {
            // 1. 入
            sumF += f[i];

            int x = nums[i];
            while (!minQ.isEmpty() && x <= nums[minQ.peekLast()]) {
                minQ.pollLast();
            }
            minQ.addLast(i);

            while (!maxQ.isEmpty() && x >= nums[maxQ.peekLast()]) {
                maxQ.pollLast();
            }
            maxQ.addLast(i);

            // 2. 出
            while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > k) {
                sumF -= f[left];
                left++;
                if (minQ.peekFirst() < left) {
                    minQ.pollFirst();
                }
                if (maxQ.peekFirst() < left) {
                    maxQ.pollFirst();
                }
            }

            // 3. 更新答案
            f[i + 1] = (int) (sumF % MOD);
        }

        return f[n];
    }
}

###java

class Solution {
    public int countPartitions(int[] nums, int k) {
        final int MOD = 1_000_000_007;
        int n = nums.length;
        int[] minQ = new int[n];
        int[] maxQ = new int[n];
        int minHead = 0, minTail = -1;
        int maxHead = 0, maxTail = -1;
        int[] f = new int[n + 1];
        f[0] = 1;
        long sumF = 0; // 窗口中的 f[i] 之和
        int left = 0;

        for (int i = 0; i < n; i++) {
            // 1. 入
            sumF += f[i];

            int x = nums[i];
            while (minHead <= minTail && x <= nums[minQ[minTail]]) {
                minTail--;
            }
            minQ[++minTail] = i;

            while (maxHead <= maxTail && x >= nums[maxQ[maxTail]]) {
                maxTail--;
            }
            maxQ[++maxTail] = i;

            // 2. 出
            while (nums[maxQ[maxHead]] - nums[minQ[minHead]] > k) {
                sumF -= f[left];
                left++;
                if (minQ[minHead] < left) {
                    minHead++;
                }
                if (maxQ[maxHead] < left) {
                    maxHead++;
                }
            }

            // 3. 更新答案
            f[i + 1] = (int) (sumF % MOD);
        }

        return f[n];
    }
}

###cpp

class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        const int MOD = 1'000'000'007;
        int n = nums.size();
        deque<int> min_q, max_q;
        vector<int> f(n + 1);
        f[0] = 1;
        long long sum_f = 0; // 窗口中的 f[i] 之和
        int left = 0;

        for (int i = 0; i < n; i++) {
            int x = nums[i];
            // 1. 入
            sum_f += f[i];

            while (!min_q.empty() && x <= nums[min_q.back()]) {
                min_q.pop_back();
            }
            min_q.push_back(i);

            while (!max_q.empty() && x >= nums[max_q.back()]) {
                max_q.pop_back();
            }
            max_q.push_back(i);

            // 2. 出
            while (nums[max_q.front()] - nums[min_q.front()] > k) {
                sum_f -= f[left];
                left++;
                if (min_q.front() < left) {
                    min_q.pop_front();
                }
                if (max_q.front() < left) {
                    max_q.pop_front();
                }
            }

            // 3. 更新答案
            f[i + 1] = sum_f % MOD;
        }

        return f[n];
    }
};

###go

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]
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。每个下标至多入队出队各两次。
空间复杂度：$\mathcal{O}(n)$。

相似题目

2762. 不间断子数组

更多相似题目，见下面动态规划题单的「§5.2 最优划分」和「§11.3 单调队列优化 DP」。

分类题单

如何科学刷题？

我的题解精选（已分类）

阅读视图

O(n^2) 做法

O(n) 做法

复杂度分析

相似题目

分类题单