目标
给你一个整数数组 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
思路
划分数组 nums，使得每一个子数组的最大最小值之差不超过 k，求划分的总方法数。
定义 dp[i] 表示 [0, i] 满足条件的划分数，dp[i + 1] = Σdp[j] j∈[l, i]，l 是固定右端点后满足条件的最小下标。
枚举满足条件的最小下标时可以使用滑动窗口，使用单调栈来维护窗口的最大值与最小值。
代码
/**
* @date 2025-12-09 9:38
*/
public class CountPartitions3578 {
public int countPartitions(int[] nums, int k) {
Deque<Integer> max = new ArrayDeque<>();
Deque<Integer> min = new ArrayDeque<>();
int mod = 1000000007;
int n = nums.length;
long[] dp = new long[n + 1];
dp[0] = 1;
int l = 0;
long window = 0;
for (int r = 0; r < n; r++) {
while (!max.isEmpty() && max.peekLast() < nums[r]) {
max.pollLast();
}
while (!min.isEmpty() && min.peekLast() > nums[r]) {
min.pollLast();
}
max.offer(nums[r]);
min.offer(nums[r]);
int diff = max.peek() - min.peek();
window += dp[r];
while (l <= r && diff > k) {
if (max.peek() == nums[l]) {
max.poll();
}
if (min.peek() == nums[l]) {
min.poll();
}
diff = max.peek() - min.peek();
window -= dp[l++];
}
dp[r + 1] = window % mod;
}
return (int) (dp[n] % mod);
}
}
性能
