MediumRating 2033

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

arraydynamic-programmingqueuesliding-windowprefix-summonotonic-queue

解題說明

Count Partitions With Max-Min Difference at Most K

題目描述：給定一個整數陣列 nums 和整數 k，將陣列劃分為若干連續子陣列，要求每個子陣列中最大值與最小值之差不超過 k。求所有合法劃分方式的數量，結果對 10^9 + 7 取模。

解題思路：使用動態規劃。令 dp[i] 表示前 i 個元素的合法劃分數。轉移式為：dp[i] = sum(dp[j]) for all j where max(nums[j+1..i]) - min(nums[j+1..i]) <= k。對於每個 i，需要找到最左邊的合法起始位置 left，使得 nums[left..i] 的 max-min <= k。可以用單調佇列（遞減佇列維護最大值、遞增佇列維護最小值）來高效維護滑動窗口的 max 和 min，再用前綴和加速 dp 值的區間求和。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個元素最多進出單調佇列一次，前綴和查詢 O(1)。

空間複雜度：O(n) — dp 陣列、前綴和陣列、單調佇列。

虛擬碼

1. Initialize dp[0] = 1, prefix sum array
2. Maintain two monotonic deques: maxQ (decreasing) and minQ (increasing)
3. For each index i from 0 to n-1:
   a. Push i onto maxQ and minQ (maintaining monotonicity)
   b. While max(window) - min(window) > k: advance left pointer, pop expired indices from deques
   c. dp[i+1] = prefix[i+1] - prefix[left] (mod 10^9+7)
   d. Update prefix sum: prefix[i+2] = prefix[i+1] + dp[i+1]
4. Return dp[n]

其他解法

線段樹 + DP O(n log n)：用線段樹維護區間 max 和 min，對每個 i 二分搜尋最左合法位置 left，然後用線段樹查詢 dp 值的區間和。比單調佇列 + 前綴和多一個 log 因子。

暴力 DP O(n²)：對每個 i，向左掃描所有合法的 j，累加 dp[j]。直覺但在 n 較大時超時。

延伸思考

如果要求每個子陣列的長度至少為 L，該如何修改 DP 轉移？
如果改為「最大值與最小值之差恰好等於 k」，問題會如何變化？
若陣列允許非連續劃分（子集劃分），問題的複雜度會如何提升？

Count Partitions With Max-Min Difference at Most K — CaffeCode