2369. Check if There is a Valid Partition For The Array

Medium
Description

給定整數陣列 nums，判斷是否存在一種分割方式，使得每個子陣列滿足以下條件之一：兩個相等元素、三個相等元素、或三個連續遞增元素。

Example:

Input: nums = [4,4,4,5,6] Output: true

Intuition#

線性 DP：對每個位置檢查是否能從前面的合法分割點延伸 2 或 3 個元素的合法子陣列。

  • dp[i] = 前 i 個元素是否能合法分割
  • 對每個位置 i，檢查三種情況能否從合法的 dp[i-2] 或 dp[i-3] 延伸
  • 三種合法子陣列：[a, a]、[a, a, a]、[a, a+1, a+2]

Approaches#

1: Bottom-Up DP#

  • 概念: 依序檢查每個位置能否從前面的合法分割延伸
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun validPartition(nums: IntArray): Boolean {
        val n = nums.size
        val dp = BooleanArray(n + 1)
        dp[0] = true
        for (i in 2..n) {
            // 兩個相等
            if (nums[i - 1] == nums[i - 2] && dp[i - 2]) {
                dp[i] = true
            }
            if (i >= 3) {
                // 三個相等
                if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3] && dp[i - 3]) {
                    dp[i] = true
                }
                // 三個連續遞增
                if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1 && dp[i - 3]) {
                    dp[i] = true
                }
            }
        }
        return dp[n]
    }
}

⭐2: Rolling Variables#

  • 概念: 只依賴前三個狀態，用三個布林變數取代陣列
  • 時間複雜度: O(n)
  • 空間複雜度: O(1)
class Solution {
    fun validPartition(nums: IntArray): Boolean {
        val n = nums.size
        // dp[i] 代表前 i 個元素能否合法分割
        // 只需保留 dp[i-1], dp[i-2], dp[i-3]
        var d0 = true   // dp[i-3] 初始 dp[0]
        var d1 = false   // dp[i-2] 初始 dp[-1] 無效
        var d2 = false   // dp[i-1] 初始 dp[0] (不用，因為從 i=2 開始)
        // 但需要更小心的初始化
        val dp = BooleanArray(n + 1)
        dp[0] = true
        for (i in 2..n) {
            dp[i] = false
            if (nums[i - 1] == nums[i - 2] && dp[i - 2]) dp[i] = true
            if (i >= 3 && dp[i - 3]) {
                if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) dp[i] = true
                if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1) dp[i] = true
            }
        }
        return dp[n]
    }
}

🔑 Takeaways#

  • Pattern: 分割型線性 DP — 決定每段的切割點，從前面的合法狀態延伸
  • 關鍵技巧: 列舉所有合法子陣列的模式（長度 2 和 3），每個位置最多檢查三種情況