题目描述

有N个多米诺牌排在一条线上，然后我们把它们竖直放着。在最开始，我们同时把某些牌向左或向右推。每一秒，每个向左倒的牌会将相邻的左边的牌向左推，相似地，每个向右倒的牌都会把右边相邻的牌向右推。当一个垂直的多米诺牌被两边的牌同时向左向右推的时候，它就会依旧保持竖直。
在这道题中，我们认为已经倒下的牌不会再给后续的牌施加推力（即认为每个牌只影响与它相邻的一块牌）。
给定字符串S代表初始状态，S[i]=’L’表示第i块牌被向左推，S[i]=’R’表示第i块牌被向右推，S[i]=’.’表示第i块牌没有被推。
返回最后的状态。

样例

输入: ".L.R...LR..L.."
输出: "LL.RR.LLRRLL.."
说明：如下图所示

输入: "RR.L"
输出: "RR.L"
说明: 第一块向右倒的牌只会影响第二块牌，不会再继续往下影响。

算法1

(模拟) $O(n)$

遍历一次字符串，如果当前字符是’.’，那么跳过，如果当前字符是’L’，判断上一次字符last是什么，如果last是’L’，那么就把last到当前字符位置的字符全部赋值为’L’，如果last是’R’，那么前面一半位置赋值为’R’,后面一半位置赋值为’L’，中间赋值为’.’，最后更新last为当前的字符。当前字符是’R’时，如果last是’R’,那么把last到当前字符位置全部赋值为’R’, 如果last是’L’，那么则不做处理（因为last向左倒，当前向右倒），最后更新last的字符和位置。

时间复杂度分析：需要扫描一遍数组，复杂度为$O(n)$

C++ 代码

class Solution {
public:
    string pushDominoes(string dominoes) {
        int lastpos = -1;
        char lastchar = ' ';
        string res = dominoes;
        for(int i = 0;i<dominoes.size();i++){
            if(dominoes[i]=='.')
                continue;
            if(dominoes[i]=='L'){
                if(lastpos<0||lastchar=='L'){
                    if(lastpos<0)
                        lastpos = 0;
                    for(int j = lastpos;j<=i;j++)
                        res[j] = 'L';
                }
                if(lastchar=='R'){
                    int l = lastpos, r = i;
                    while(l<r){
                        res[l] = 'R';
                        res[r] = 'L';
                        l++;
                        r--;
                    }
                }
                lastpos = i;
                lastchar = 'L';
            }
            if(dominoes[i]=='R'){
                if(lastpos>=0&&lastchar=='R'){
                    for(int j = lastpos;j<=i;j++)
                        res[j] = 'R';
                }
                lastpos = i;
                lastchar = 'R';
            }
        }
        if(lastpos>=0&&lastchar=='R'){//注意如果最后的last是R，那么会从last的位置一直到结尾都是R
            for(int j = lastpos;j<dominoes.size();j++)
                res[j] = 'R';
        }
        return res;
    }
};