HardRating 2345
3826. Minimum Partition Score
arraydivide-and-conquerdynamic-programmingqueueprefix-summonotonic-queue
解題說明
Minimum Partition Score
題目描述：給定一個整數陣列 nums 和整數 k，將陣列劃分為恰好 k 個連續子陣列。每個子陣列的「分數」為其最大值與最小值之差。整體分數為所有子陣列分數的最大值。求最小化整體分數。
解題思路：二分搜尋答案。二分搜尋整體分數的目標值 mid，然後驗證是否能將陣列劃分為至多 k 個子陣列，使得每個子陣列的 max - min <= mid。
驗證函數使用貪心策略：從左到右掃描，盡可能讓每個子陣列越長越好。使用兩個變數追蹤當前子陣列的 max 和 min，當 max - min > mid 時，切斷並開始新的子陣列。若切斷次數 < k，則 mid 可行。
但要注意：當需要恰好 k 段時，貪心的「盡量長」策略可能不是最優的。此時需要用 DP + 單調佇列的方法，或者觀察到：若能分成 <= k 段（每段 max-min <= mid），也一定能恰好分成 k 段。
C++ 解法
複雜度分析
時間複雜度：O(n log D) — D 為陣列的值域範圍（max - min）。二分搜尋 O(log D) 層，每層貪心驗證 O(n)。
空間複雜度：O(1) — 只需常數額外空間。
虛擬碼
1. Binary search on answer `mid` (range: 0 to max(nums) - min(nums)) 2. For each `mid`, validate with greedy: a. Scan left to right, track current subarray's max and min b. When max - min > mid: start new subarray, increment parts count c. If parts <= k: feasible 3. Return minimum feasible `mid`
其他解法
DP + 單調佇列 O(n * k)：令 dp[i][j] = 前 i 個元素分成 j 段的最小最大分數。轉移需要枚舉最後一段的起點，用單調佇列優化到 O(1) 攤銷轉移。適合 k 較小的情況。
分治法：將陣列分為兩半，分別求解後合併。但合併步驟需要考慮跨越中點的劃分，較為複雜。
延伸思考
- 如果分數定義為子陣列的標準差（而非極差），如何二分搜尋驗證？
- 若劃分不要求連續（可以任意選元素組成子集），問題如何變化？
- 如果每個子陣列有長度上限 L，如何在驗證函數中加入此約束？