MediumRating 1780
2369. Check if There is a Valid Partition For The Array
arraydynamic-programming
解題說明
Check if There is a Valid Partition For The Array
題目描述:
給定一個整數陣列 nums,判斷是否存在一種合法的分割方式,將陣列分成一個或多個子陣列,其中每個子陣列滿足以下其一:
- 恰好 2 個相等的元素
- 恰好 3 個相等的元素
- 恰好 3 個連續遞增的元素(差值為 1)
解題思路: 使用動態規劃:
- 定義
dp[i]=nums[0..i-1](前 i 個元素)是否可以合法分割。 - 轉移條件(對於
dp[i]):- 若
nums[i-1] == nums[i-2]且dp[i-2]為 true →dp[i] = true(2 個相等) - 若
i >= 3且nums[i-1] == nums[i-2] == nums[i-3]且dp[i-3]為 true →dp[i] = true(3 個相等) - 若
i >= 3且nums[i-1] == nums[i-2]+1 == nums[i-3]+2且dp[i-3]為 true →dp[i] = true(3 個連續遞增)
- 若
- 基底:
dp[0] = true(空陣列可分割)。 - 答案為
dp[n]。
C++ 解法
複雜度分析
時間複雜度:O(n) — 單次遍歷陣列。
空間複雜度:O(n) — DP 陣列大小為 n+1。可用滾動變數優化至 O(1)。
虛擬碼
1. Initialize dp[0..n] = false, dp[0] = true
2. For i from 2 to n:
a. If nums[i-1] == nums[i-2] and dp[i-2]: dp[i] = true
b. If i >= 3:
- If nums[i-1] == nums[i-2] == nums[i-3] and dp[i-3]: dp[i] = true
- If nums[i-1] == nums[i-2]+1 == nums[i-3]+2 and dp[i-3]: dp[i] = true
3. Return dp[n]其他解法
滾動變數 O(1) 空間:由於 dp[i] 只依賴 dp[i-2] 和 dp[i-3],可以用 3 個變數代替整個陣列。
遞迴 + 記憶化 O(n):自頂向下嘗試從位置 0 開始,每次選擇切出 2 或 3 個元素的子陣列。邏輯直觀但有遞迴開銷。
延伸思考
- 如果允許的子陣列模式增加(例如 4 個相等或 4 個連續遞增),DP 轉移如何擴展?
- 如何輸出一種合法的分割方案(而非僅判斷是否存在)?
- 如果元素可以重新排列後再分割,問題的性質如何改變?