LeetCode 838. 推多米诺
题目描述
题意分析
L、R表示初始向左或向右受推的骨牌，.表示直立。所有推力以每秒一格的速度同时传播；直立骨牌若同时受到两侧相反推力，会保持直立。已经倒下或正在倒下的骨牌不会再改变方向，求最终状态。
解法：按相邻推力之间的区间分类填充
核心思路
[!blue]
将连续的点号按两侧最近的初始
L、R分段。这段内部没有初始推力，外侧的影响又不能穿过已经受推的端点改变它，所以中间状态只由相邻两个非点字符决定，不必逐秒模拟。
- 两端同为
L：右端的推力向左传播，整段填L。- 两端同为
R：左端的推力向右传播，整段填R。- 左端为
L、右端为R：两边都向外倒，中间保持直立。- 左端为
R、右端为L：两股推力相向传播。更靠左的位置先受右推，更靠右的位置先受左推；用双指针从两侧向中间分别填R、L。若剩下一个等距中心，两股力同时到达，保留原来的点号。用
left、previous保存上一推力的位置与方向，right扫描下一个非点字符。找到右端后才填充开区间(left, right)，修改的都是已经扫描过的位置，不会把新填入的字符误当成后续初始推力。首尾缺少一侧端点时，用下标
-1的虚拟L与下标n的虚拟R统一处理。它们都向区间外侧，不会凭空产生向内推力：开头的点号仅在第一个非点字符为L时向左倒，末尾的点号仅在最后一个非点字符为R时向右倒；全是点号时则保持不变。虚拟端点只参与分类，不写入数组。
解题步骤
- 将输入复制成可修改字符数组，令
left = -1、previous = L。- 从左到右扫描，遇到点号继续；扫描到
n时把当前方向视为虚拟R。- 两端方向相同则填满中间区间；左
R右L时从两边向中间填充；左L右R时不修改。- 将当前右端保存为下一段的左端，直到末尾区间也处理完。
- 返回字符数组组成的字符串。
代码实现
class Solution {
public String pushDominoes(String dominoes) {
char[] result = dominoes.toCharArray();
int left = -1;
int n = result.length;
char previous = 'L';
for (int right = 0; right <= n; right++) {
char current = right == n ? 'R' : result[right];
if (current == '.') {
continue;
}
if (previous == current) {
for (int i = left + 1; i < right; i++) {
result[i] = current;
}
} else if (previous == 'R' && current == 'L') {
int i = left + 1;
int j = right - 1;
while (i < j) {
result[i++] = 'R';
result[j--] = 'L';
}
}
left = right;
previous = current;
}
return new String(result);
}
}
func pushDominoes(dominoes string) string {
result := []byte(dominoes)
left, n := -1, len(result)
previous := byte('L')
for right := 0; right <= n; right++ {
current := byte('R')
if right < n {
current = result[right]
}
if current == '.' {
continue
}
if previous == current {
for i := left + 1; i < right; i++ {
result[i] = current
}
} else if previous == 'R' && current == 'L' {
i, j := left+1, right-1
for i < j {
result[i] = 'R'
result[j] = 'L'
i++
j--
}
}
left = right
previous = current
}
return string(result)
}
复杂度分析
- 时间复杂度：$O(n)$，主指针扫描一次，各段内部互不重叠，每个位置最多被填充一次。
- 空间复杂度：$O(n)$，保存可修改的结果字符数组。
关键点总结
[!green]
四种端点关系决定每段最终状态；相向推力按到达距离决定方向，等距中心保持直立。虚拟端点用于统一首尾分支，不代表实际新增骨牌。
易错点总结
[!yellow]
- R…L 的中间一个位置受力同时抵消，应保留 .。
- L…R 是背向传播，中间不能填成 L 或 R。
- 虚拟端点只参与判断，不能写入下标 -1 或 n。
相似题目
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！