838. Push Dominoes

Medium

Description

給定字串 dominoes，其中 'L' 表示向左推、'R' 表示向右推、'.' 表示未被推。模擬骨牌倒下的最終狀態。同時被左右推的骨牌保持直立。

Example:

Input: dominoes = “.L.R…LR..L..” Output: “LL.RR.LLRRLL..”

Intuition#

核心思路：計算每個位置受到左推力和右推力的距離，距離越近力量越大。比較兩側的力量決定最終方向。

另一個思路：找出相鄰的力源（R 或 L），分析它們之間的區段
- R...L：兩端向中間倒，中間保持直立（若距離為偶數）
- R...R：全部向右倒
- L...L：全部向左倒
- L...R：中間保持不動

Approaches#

1: Force Simulation (Distance Array)#

概念: 從左到右計算右推力距離，從右到左計算左推力距離，比較兩個力決定最終狀態
時間複雜度: O(n) - 兩次遍歷
空間複雜度: O(n) - 力量陣列

class Solution {
    fun pushDominoes(dominoes: String): String {
        val n = dominoes.length
        val forces = IntArray(n)

        // 從左到右：R 的力量隨距離遞減
        var force = 0
        for (i in 0 until n) {
            if (dominoes[i] == 'R') force = n
            else if (dominoes[i] == 'L') force = 0
            else force = maxOf(force - 1, 0)
            forces[i] += force
        }

        // 從右到左：L 的力量隨距離遞減
        force = 0
        for (i in n - 1 downTo 0) {
            if (dominoes[i] == 'L') force = n
            else if (dominoes[i] == 'R') force = 0
            else force = maxOf(force - 1, 0)
            forces[i] -= force
        }

        val sb = StringBuilder()
        for (f in forces) {
            sb.append(if (f > 0) 'R' else if (f < 0) 'L' else '.')
        }
        return sb.toString()
    }
}

⭐2: Two Pointers (Segment Analysis)#

概念: 在字串前後加上哨兵 'L' 和 'R'，用雙指標找每對相鄰力源，分析中間區段
時間複雜度: O(n) - 一次遍歷
空間複雜度: O(n) - 結果陣列（可視為 O(1) 額外空間）

class Solution {
    fun pushDominoes(dominoes: String): String {
        val s = "L${dominoes}R"  // 加上哨兵
        val result = CharArray(s.length)
        var left = 0

        for (right in 1 until s.length) {
            if (s[right] == '.') continue

            // 填充 left 和 right 之間的區段
            if (s[left] == s[right]) {
                // 同方向：全部填同一方向
                for (k in left..right) result[k] = s[left]
            } else if (s[left] == 'L' && s[right] == 'R') {
                // L...R：中間保持直立
                for (k in left..right) result[k] = '.'
                result[left] = 'L'
                result[right] = 'R'
            } else {
                // R...L：兩端向中間倒
                for (k in left..right) {
                    val distLeft = k - left
                    val distRight = right - k
                    result[k] = when {
                        distLeft < distRight -> 'R'
                        distLeft > distRight -> 'L'
                        else -> '.'
                    }
                }
            }
            left = right
        }

        return String(result, 1, dominoes.length)  // 去掉哨兵
    }
}

哨兵技巧：在字串前加 'L'、後加 'R'，確保邊界的 '.' 也能被正確處理。最後取結果時要去掉哨兵部分。

🔑 Takeaways#

Pattern: 區段分析問題 -> 找分隔點 + 分類處理每個區段
關鍵技巧: 哨兵簡化邊界處理；Force Simulation 的正負力量抵消是一種優雅的建模方式，可推廣到其他「雙向影響」問題