Medium

题目描述

给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个非空连续段，使得每个段中最大值和最小值的差值不超过 k。

返回满足此条件的分割 nums 的方案总数。

由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：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]]

示例 2：

输入：nums = [3,3,4], k = 0
输出：2
解释：
有 2 种满足条件的有效分割方案：
[[3], [3], [4]]
[[3, 3], [4]]

约束条件：

  • 2 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

解题思路

这道题需要用动态规划结合滑动窗口来解决。

核心思路： 定义 dp[i] 表示以位置 i 结尾的所有有效分割方案数。对于每个位置 i，我们需要找到所有可能的起始位置 j，使得区间 [j, i] 满足最大值与最小值的差值不超过 k。

关键技术：

  1. 滑动窗口：对于每个结尾位置 i，使用滑动窗口向左扩展找到最长的有效区间
  2. 单调双端队列：维护窗口内的最大值和最小值
    • 用单调递减队列维护最大值
    • 用单调递增队列维护最小值
  3. 动态规划状态转移：dp[i] = sum(dp[j-1]) 对于所有有效的起始位置 j

算法流程：

  1. 初始化 dp[0] = 1（空前缀有一种方案）
  2. 对于每个位置 i，使用滑动窗口找到最长的有效区间 [left, i]
  3. 将区间内所有可能的起始位置对应的方案数累加到 dp[i+1]
  4. 使用前缀和优化区间求和操作

时间复杂度为 O(n)，因为每个元素最多进出队列一次。

代码实现

class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        vector<long long> dp(n + 1, 0);
        dp[0] = 1;
        
        for (int i = 0; i < n; i++) {
            deque<int> maxDq, minDq;
            int left = i;
            
            for (int j = i; j >= 0; j--) {
                // 维护最大值队列（单调递减）
                while (!maxDq.empty() && nums[maxDq.back()] <= nums[j]) {
                    maxDq.pop_back();
                }
                maxDq.push_back(j);
                
                // 维护最小值队列（单调递增）
                while (!minDq.empty() && nums[minDq.back()] >= nums[j]) {
                    minDq.pop_back();
                }
                minDq.push_back(j);
                
                // 检查当前窗口是否有效
                if (nums[maxDq.front()] - nums[minDq.front()] <= k) {
                    left = j;
                } else {
                    break;
                }
            }
            
            // 计算以i结尾的所有有效分割方案数
            for (int j = left; j <= i; j++) {
                dp[i + 1] = (dp[i + 1] + dp[j]) % MOD;
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(n):
            max_dq = deque()
            min_dq = deque()
            left = i
            
            for j in range(i, -1, -1):
                # 维护最大值队列（单调递减）
                while max_dq and nums[max_dq[-1]] <= nums[j]:
                    max_dq.pop()
                max_dq.append(j)
                
                # 维护最小值队列（单调递增）
                while min_dq and nums[min_dq[-1]] >= nums[j]:
                    min_dq.pop()
                min_dq.append(j)
                
                # 检查当前窗口是否有效
                if nums[max_dq[0]] - nums[min_dq[0]] <= k:
                    left = j
                else:
                    break
            
            # 计算以i结尾的所有有效分割方案数
            for j in range(left, i + 1):
                dp[i + 1] = (dp[i + 1] + dp[j]) % MOD
        
        return dp[n]

public class Solution {
    public int CountPartitions(int[] nums, int k) {
        const int MOD = 1000000007;
        int n = nums.Length;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 0; i < n; i++) {
            var maxDq = new LinkedList<int>();
            var minDq = new LinkedList<int>();
            int left = i;
            
            for (int j = i; j >= 0; j--) {
                // 维护最大值队列（单调递减）
                while (maxDq.Count > 0 && nums[maxDq.Last.Value] <= nums[j]) {
                    maxDq.RemoveLast();
                }
                maxDq.AddLast(j);
                
                // 维护最小值队列（单调递增）
                while (minDq.Count > 0 && nums[minDq.Last.Value] >= nums[j]) {
                    minDq.RemoveLast();
                }
                minDq.AddLast(j);
                
                // 检查当前窗口是否有效
                if (nums[maxDq.First.Value] - nums[minDq.First.Value] <= k) {
                    left = j;
                } else {
                    break;
                }
            }
            
            // 计算以i结尾的所有有效分割方案数
            for (int j = left; j <= i; j++) {
                dp[i + 1] = (dp[i + 1] + dp[j]) % MOD;
            }
        }
        
        return (int)dp[n];
    }
}

var countPartitions = function(nums, k) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    
    for (let i = 0; i < n; i++) {
        const maxDq = [];
        const minDq = [];
        let left = i;
        
        for (let j = i; j >= 0; j--) {
            // 维护最大值队列（单调递减）
            while (maxDq.length > 0 && nums[maxDq[maxDq.length - 1]] <= nums[j]) {
                maxDq.pop();
            }
            maxDq.push(j);
            
            // 维护最小值队列（单调递增）
            while (minDq.length > 0 && nums[minDq[minDq.length - 1]] >= nums[j]) {
                minDq.pop();
            }
            minDq.push(j);
            
            // 检查当前窗口是否有效
            if (nums[maxDq[0]] - nums[minDq[0]] <= k) {
                left = j;
            } else {
                break;
            }
        }
        
        // 计算以i结尾的所有有效分割方案数
        for (let j = left; j <= i; j++) {
            dp[i + 1] = (dp[i + 1] + dp[j]) % MOD;
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)对于每个位置i，最坏情况下需要遍历所有前面的位置来计算有效区间和累加dp值
空间复杂度O(n)dp数组占用O(n)空间，双端队列最多存储O(n)个元素

相关题目