题目大意：
推多米诺
一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。
在开始时，我们同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。
同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。
就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。
给定表示初始状态的字符串 “S” 。如果第 i 张多米诺骨牌被推向左边，则 S[i] = ‘L’；如果第 i 张多米诺骨牌被推向右边，则 S[i] = ‘R’；如果第 i 张多米诺骨牌没有被推动，则 S[i] = ‘.’。
返回表示最终状态的字符串。
示例 1：
输入：".L.R...LR..L.." 输出："LL.RR.LLRRLL.."
示例 2：
输入："RR.L" 输出："RR.L" 说明：第一张多米诺骨牌没有给第二张施加额外的力。
提示：
0 <= N <= 10^5- 表示多米诺骨牌状态的字符串只含有
'L'，'R'; 以及'.';
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=838
解题思路分析：
这道题需要考虑清楚一个问题即可轻松解题。对于初始时被推动的牌是无法再次改变其状态的，因此可能改变状态的只有仍处于垂直状态的牌，也就是字符串中为”.”的部分。对于任意一个多米诺骨牌，其最终的状态取决于在它左边距离它最近的向右倒下的牌，以及在它右边距离它最近的向左倒下的牌，哪一个距离更近，它的最终状态就是距离他更近的那一张牌倒下的方向。如果两边距离相同，那么他将仍然保持垂直状态。
因此解题时需要以下步骤。
- 从左至右循环一遍字符串，如果当前字符为”.”，记录下他与左边最近的R的距离：（i-RIndex），如果左边还没出现过R，那么距离设为无穷大。如果当前字符为R，记住当前R的下标（ RIndex = i）。如果当前字符为L，更新 RIndex 为无穷大。
- 同理从右至左循环一遍字符串，记录下”.”与右方最近的L的距离。
- 最后再循环一遍字符串，如果当前字符为L或者R，直接加入返回结果。如果当前字符是”.”，查看其距左方的R的距离以及距右方L的距离，如果左方的距离小，将R加入返回结果，反之将L加入返回结果。
实现代码：
public String pushDominoes(String dominoes) {
// 所有点距离左方最近的R的长度
int[] leftDis= new int[dominoes.length()];
// 所有点距离右方最近的L的长度
int[] rightDis= new int[dominoes.length()];
// 将字符串转为数组。
char[] res=dominoes.toCharArray();
// 最近的R的下标
int rightIndex=Integer.MAX_VALUE;
// 循环字符串
for(int i=0;i<dominoes.length();i++){
char c = res[i]; // 当前字符
if(c=='.'){ // 如果是点
// 查看当前下标与rightIndex间的距离。
// 如果rightIndex为无穷大，那么距离就是无穷大
rightDis[i]=
rightIndex==Integer.MAX_VALUE?Integer.MAX_VALUE:i-rightIndex;
}else if(c=='R'){
// 如果当前字符是R，更新rightIndex为当前下标
rightIndex=i;
}else{
// 如果当前字符是L，更新rightIndex为无穷大
rightIndex=Integer.MAX_VALUE;
}
}
// 同理
int leftIndex=Integer.MAX_VALUE;
for(int i=dominoes.length()-1;i>=0;i--){
char c = res[i];
if(c=='.'){
leftDis[i]=leftIndex==Integer.MAX_VALUE?Integer.MAX_VALUE:leftIndex-i;
}else if(c=='L'){
leftIndex=i;
}else{
leftIndex=Integer.MAX_VALUE;
}
}
// 返回结果
StringBuilder sb=new StringBuilder();
// 循环字符串
for(int i=0;i<dominoes.length();i++){
// 如果当前字符是点
if(res[i]=='.'){
// 查看其距离左边的R近还是距离右边的L近
if(leftDis[i]<rightDis[i]){
sb.append('L');
}else if(leftDis[i]>rightDis[i]){
sb.append('R');
}else{
sb.append('.');
}
}else{
// 如果是L或R，直接加入返回结果
sb.append(res[i]);
}
}
return sb.toString();
}本题解法执行时间为14ms。
Runtime: 14 ms, faster than 49.73% of Java online submissions for Push Dominoes.
Memory Usage: 38.1 MB, less than 100.00% of Java online submissions for Push Dominoes.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-838-push-dominoes-解题思路分析/