Leetcode 3578. Count Partitions With Max-Min Difference at Most K

• Leetcode 3578. Count Partitions With Max-Min Difference at Most K
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3578. Count Partitions With Max-Min Difference at Most K

1. 解题思路

这一题是一个动态规划的思路，不过我也是卡了一下，因为需要对动态规划的过程进行一下聚合，直接做会遇到超时的问题，后来是看了一下deepseek的解答搞定了，这里就不多说了，实在有点伤自尊……

2. 代码实现

给出python代码实现如下：

MOD = 10**9+7class Solution:def countPartitions(self, nums: List[int], k: int) -> int:n = len(nums)if max(nums) - min(nums) <= k:return pow(2, n-1, mod=MOD)dp = [1, 1] + [0 for _ in range(n-1)]accum_dp = [0, 1, 2] + [0 for _ in range(n-1)] cache = [(nums[0], 0)]left = -1for i in range(1, n):while cache and nums[i] - cache[0][0] > k:_, idx = cache.pop(0)left = max(left, idx)while cache and cache[-1][0] - nums[i] > k:_, idx = cache.pop()left = max(left, idx)bisect.insort(cache, (nums[i], i))dp[i+1] = (accum_dp[i+1] - accum_dp[left+1]) % MODaccum_dp[i+2] = (accum_dp[i+1] + dp[i+1]) % MODreturn dp[-1] % MOD

提交代码评测得到：耗时964ms，占用内存29.5MB。