[每日一题]151：推多米诺

题目描述

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

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

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

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

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

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

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

示例 1：

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

示例 2：

输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

提示：

• n == dominoes.length
• 1 <= n <= 105
• dominoes[i] 为 ‘L’、‘R’ 或 ‘.’

题解思路

方法一：模拟

我们可以枚举所有连续的没有被推动的骨牌，根据这段骨牌的两边骨牌（如果有的话）的推倒方向决定这段骨牌的最终状态：

• 如果两边的骨牌同向，那么这段连续的竖立骨牌会倒向同一方向。
• 如果两边的骨牌相对，那么这段骨牌会向中间倒。
• 如果两边的骨牌相反，那么这段骨牌会保持竖立。

特别地，如果左侧没有被推倒的骨牌，则假设存在一块向左倒的骨牌；如果右侧没有被推倒的骨牌，则假设存在一块向右倒的骨牌。这样的假设不会破坏骨牌的最终状态，并且边界情况也可以落入到上述三种情况中。

我们可以使用两个指针 i 和 j 来枚举所有连续的没有被推动的骨牌，left 和 right 表示两边骨牌的推倒方向。根据上述三种情况来计算骨牌的最终状态。

代码如下：

class Solution {
public:string pushDominoes(string dominoes) {int n = dominoes.size(), i = 0;char left = 'L';while(i < n) {int j = i;while (j < n && dominoes[j] == '.') {   // 找到一段连续的没有被推动的骨牌++j;}char right = j < n ? dominoes[j] : 'R';if (left == right) {    // 方向相同，那么这些竖立骨牌也会倒向同一方向while (i < j) {dominoes[i++] = right;}}else if (left == 'R' && right == 'L') { // 方向相对，那么就从两侧向中间倒int k = j - 1;while (i < k) {dominoes[i++] = 'R';dominoes[k--] = 'L';}}left = right;i = j + 1;}return dominoes;}
};

复杂度分析

• 时间复杂度：$O(n)$，其中 n 是 dominoes 的长度。每个下标会最多会被访问和赋值各一次。
• 空间复杂度：$O(n)$。