838. 推多米诺

题目

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' 或 '.'

思路

挺有意思的题目，自己没做出来，学习一下官解吧。思路是从左往右找连续的没有被推倒的牌，找好后看左右两边的牌的朝向，如果相同，则这些所有没有被推倒的牌都会变为这个，如果左边的向右推，右边的向左推，则没有被推的牌向中间倾倒。具体实现细则写在注释里了。

代码

class Solution {
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        char[] arr = dominoes.toCharArray();
        // left表示没推倒牌的左边牌的朝向
        // 这里初始化为'L’ 可以想象成最左边加一块朝左倒的牌 这样省去了边界判断
        char left = 'L';
        for (int i = 0; i < n; i++) {
            // j为连续没推倒牌的右边牌
            int j = i;
            while (j < n && arr[j] == '.') {
                j++;
            }
            // right表示没推倒牌的右边牌的朝向
            // 同样如果j等于n时 想象右边加一块朝右倒的牌
            char right = j == n ? 'R' : arr[j];
            // 左右两边朝向一样
            if (left == right) {
                for (int k = i; k < j; k++) {
                    arr[k] = left;
                }
            } else if (left == 'R' && right == 'L') { // 左边的向右推，右边的向左推
                // 将[i, j-1]之间的牌向中间靠拢推到
                // 使用k变量是为了将j存下来 之后用于更新i
                int k = j - 1;
                while (i < k) {
                    arr[i++] = 'R';
                    arr[k--] = 'L';
                }
            }
            // i更新成j 即现在的右边界下次变成左边界 循环体里i还会++ j+1的位置刚好是需要在下个循环一开始判断的
            i = j;
            left = right;
        }
        return new String(arr);
    }
}