目标
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 <= 10^5
- dominoes[i] 为 'L'、'R' 或 '.'
思路
已知多米诺骨牌的初始状态，求最终状态。
分类讨论，使用变量 prevIndex 记录前一个非 '.' 的位置，根据 prev = chars[prevIndex] 与 cur = chars[curIndex] 来填充 (prevIndex, curIndex)。
- prev = 'R'，cur = 'R'，填充为 'R'
- prev = 'R'，cur = 'L'，前半部分填充 'R'，后半部分填充 'L'
- prev = 'L'，cur = 'L'，填充为 'L'
- prev = 'L'，cur = 'R'，保持不变
代码
/**
* @date 2025-05-02 22:06
*/
public class PushDominoes838 {
public String pushDominoes(String dominoes) {
char[] chars = dominoes.toCharArray();
int n = chars.length;
int prevIndex = -1;
char prev = 'L';
char[] res = dominoes.toCharArray();
for (int curIndex = 0; curIndex <= n; curIndex++) {
char cur;
if (curIndex == n) {
cur = 'R';
} else {
cur = chars[curIndex];
}
if (prev == 'R' && cur == 'L') {
int cnt = (curIndex - 1 - prevIndex) / 2;
Arrays.fill(res, prevIndex + 1, prevIndex + cnt + 1, 'R');
Arrays.fill(res, curIndex - cnt, curIndex, 'L');
} else if (prev == cur) {
Arrays.fill(res, prevIndex + 1, curIndex, cur);
}
if (cur != '.') {
prevIndex = curIndex;
prev = cur;
}
}
return new String(res);
}
}
性能
