点击获取AI摘要

838. 推多米诺 M

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

  • dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
  • dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
  • dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。

返回表示最终状态的字符串。

示例 1：

输入：dominoes = “RR.L”
输出：“RR.L”
解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：

示例 2

输入：dominoes = “.L.R…LR…L…”
输出：“LL.RR.LLRRLL…”

提示：

  • n == dominoes.length
  • 1 <= n <= 10510^5
  • dominoes[i] 为 'L'、'R' 或 '.'

问题分析

有n张多米诺骨牌排成一行。

  • 当推动一些骨牌向左或向右后，每秒倒向左边的骨牌会推倒其左侧相邻骨牌，
  • 倒向右边的骨牌会推倒其右侧相邻骨牌。
  • 如果竖立骨牌的左右两侧同时有骨牌倒下，则它保持竖立。

求最后的骨牌倒向状态。

算法思路

1. 加入哨兵（Sentinel）

  • 我们在原串 dominoes 的最左端加入一个虚拟的 'L'，下标记为 0；
  • 在最右端加入一个虚拟的 'R'，下标记为 n+1。
  • 原字符串字符对应到新数组 s 的位置是 1 到 n。

这样做的好处是：无论最左或最右一侧最初如何受力，都能统一用同一套逻辑处理，无需额外分支。

原： . L . R . . . L R . . L . .
索引： 1 2 3 4 5 6 7 8 9 10 11 12 13 14
s： [L] . L . R . . . L R . . L . . [R]
索引： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  • prev 和 prevChar 初始为 0、'L'，对应哨兵左侧。
  • 我们的目标是，每当遇到一个非点字符（'L' 或 'R'）时，就处理上一次非点到当前之间的区间。

2. 区间类型与对应填充策略

设当前指针 i（范围 1…n+1）指向一个非点字符 currChar = s[i]，上一次非点在 prev、字符为 prevChar。区间 (prev, i)（不含端点）即是待处理段。共有三种情况：

prevChar currChar 说明 区间填充方式
L R 左侧向左，右侧向右——中间没人受力 保持全部 . 不变
L L 两侧都向左——向左的力传导 整段填充为 L
R R 两侧都向右——向右的力传导 整段填充为 R
R L 左右相向——中间骨牌两端受力，向中央倒；中间正中如果恰好在平衡点，则不倒 从两端向中间：左半段填 R，右半段填 L；如果区间长度为奇数，中点保留 .

特别地，R...L 的中点保持直立是因为左右对等力量平衡。

时间复杂度

O(n)O(n) ：一次从 1 扫描到 n+1，区间内填充合计仅做每个位置不超过一次写操作

空间复杂度：O(n)O(n)，使用大小为 n+2 的辅助字符数组。

代码分解

  1. 线性扫描 + 两个指针
    我们在字符串两端分别加上虚拟的多米诺骨牌，以简化边界处理：

    • 在最左端加一个假想的 L（下标 -1），
    • 在最右端加一个假想的 R（下标 n）。

  2. 记录上一次非点状态的位置和方向

    • 用 prev 存储上一个非点（'L' 或 'R'）的下标，
    • 用 prevChar 存储对应的字符。

  3. 遍历

    • 当遇到下一个非点字符 currChar（下标 i）时，考察区间 (prev, i)：
      • 如果 prevChar == currChar，则这一段内所有骨牌都倒向同一方向；
      • 如果 prevChar=='R' 且 currChar=='L'，则中间部分向两端倒：左半段倒 R，右半段倒 L；
      • 如果 prevChar=='L' 且 currChar=='R'，中间保持直立不动。
      • 更新 prev = i, prevChar = currChar，继续扫描。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        # 在头尾各加一个哨兵，简化边界
        s = ['L'] + list(dominoes) + ['R']
        prev = 0
        prevChar = 'L'
        
        for i in range(1, n + 2):
            currChar = s[i]
            if currChar == '.':
                continue
            
            # 区间 (prev, i)
            if prevChar == currChar:
                # 同向全填充
                for k in range(prev + 1, i):
                    s[k] = currChar
            elif prevChar == 'R' and currChar == 'L':
                # 两侧相向，中间向两端
                left, right = prev + 1, i - 1
                while left < right:
                    s[left] = 'R'
                    s[right] = 'L'
                    left += 1
                    right -= 1
                # 如果 left == right，保持 '.'（平衡力）
            # 如果是 L...R，保持不变
            
            prev = i
            prevChar = currChar
        
        # 拼回原始长度
        return ''.join(s[1:-1])

以 ".L.R...LR..L.." 为例（原长 14），在数组 s 上的区间索引是 1…14，我们实际扫描到 i=15 才遇到最后的 'R' 哨兵。

索引 i s[i] 内容 操作及说明 更新后 prev 值 更新后 prevChar
初始化 - s = ['L', '.', 'L', '.', 'R', '.', '.', '.', 'L', 'R', '.', '.', 'L', '.', '.', 'R']，prev = 0，prevChar = 'L' 0 L
i=1 . 跳过 0 L
i=2 L 区间 (0, 2)，只有下标 1，prevChar = 'L'，currChar = 'L'，属于 L...L → 将 s[1] 填为 L 2 L
i=3 . 跳过 2 L
i=4 R 区间 (2,4)，下标 3，prevChar = 'L'，currChar = 'R'，属于 L...R → 保持 s[3]='.' 4 R
i=5 - i=8 全为 . 跳过 4 R
i=9 L 区间 (4,9)，下标 5,6,7,8，prevChar = 'R'，currChar = 'L'，属于 R...L，长度 4，左右对称 → s[5] = R，s[8] = L；s[6] = R，s[7] = L 9 L
i=10 R 区间 (9,10)，只有 s[9.5?] 无点 → 跳过。更新 prev = 10，prevChar = 'R' 10 R
i=11 - i=12 . 跳过 10 R
i=13 L 区间 (10,13)，下标 11,12，R...L，长度 2 → s[11] = R，s[12] = L 13 L
i=14 . 跳过 13 L
i=15 R 区间 (13,15)，下标 14，L...R → 保持 '.' 15 R

最终去掉两端哨兵，拼回结果就是 "LL.RR.LLRRLL.."