推多米诺 图解题解
这道题到底在问什么
- 输入
- dominoes="RR.L"
- 输出
- "RR.L"
- 输入
- dominoes=".L.R...LR.L"
- 输出
- "LL.RR.LLR.L"
最优解：一步一步想明白
- 3记住:加哨兵 L…R,再看每对相邻受力牌之间那段怎么倒。下面一段段处理。
- 4先在两端各加一张永不倒的哨兵牌:左边一个 L、右边一个 R(画面里灰色那两张)。有了它们,最左、最右那段也能套同一套规则,不用单独写边界。
- 5扫描指针走到下标 2,这是个受力牌 L。它和上一个受力牌(下标 0 的 L)之间夹着 1 张直立牌,这一段怎么倒,就看这两端。
- 6先看这一段:两端都是 L,中间这 1 张还直立着(灰色待定)。两端同向,接下来会被一起推倒。
- 7两端是同一个方向 L,那中间这一整段都被往同一边推,全部填成 L(变绿落定)。
- 8扫描指针走到下标 4,这是个受力牌 R。它和上一个受力牌(下标 2 的 L)之间夹着 1 张直立牌,这一段怎么倒,就看这两端。
- 9先看这一段:左端是 L 往左倒、右端是 R 往右倒,两股力背对背走开。中间这 1 张被框住,接下来会确认它们原样不动。
- 10确认一下:两股力背对背,中间这段没有任何人来推,所以原样保持直立 .。
- 11扫描指针走到下标 8,这是个受力牌 L。它和上一个受力牌(下标 4 的 R)之间夹着 3 张直立牌,这一段怎么倒,就看这两端。
- 12先看这一段:左端 R 往右推、右端 L 往左推,两股力对着挤。中间这 3 张会从最外一对开始、向中间一对对地落定。
- 13从最外一对开始:第 5 位离左边的 R 近,倒成 R;第 7 位离右边的 L 近,倒成 L。再往里收一对。
- 14收到正中间,只剩第 6 位。它离左边的 R 和右边的 L 一样远,两边力气相等、谁也推不动它,保持直立 .。
- 15扫描指针走到下标 9,这是个受力牌 R。它和上一个受力牌(下标 8 的 L)之间夹着 0 张直立牌,这一段怎么倒,就看这两端。
- 16这两个受力牌挨在一起,中间一张直立牌都没有,自然什么都不用做,直接看下一段。
- 17扫描指针走到下标 11,这是个受力牌 L。它和上一个受力牌(下标 9 的 R)之间夹着 1 张直立牌,这一段怎么倒,就看这两端。
- 18先看这一段:左端 R 往右推、右端 L 往左推,两股力对着挤。中间只有第 10 位这一张,它正好卡在两股力的中点,下一步就要判它受力抵消、保持直立。
- 19收到正中间,只剩第 10 位。它离左边的 R 和右边的 L 一样远,两边力气相等、谁也推不动它,保持直立 .。
- 20扫描指针走到下标 12,这是个受力牌 R。它和上一个受力牌(下标 11 的 L)之间夹着 0 张直立牌,这一段怎么倒,就看这两端。
- 21这两个受力牌挨在一起,中间一张直立牌都没有,自然什么都不用做,直接看下一段。
- 22所有相邻受力段都处理完了,回头整串看一遍:含两端哨兵在内,整排已经稳定下来,不会再有任何牌移动。下一步只剩去掉哨兵。
- 23所有相邻受力段都处理完了。把两端的哨兵牌去掉,中间这串就是最终稳定状态 "LL.RR.LLR.L",和开头说的一致。回头看,我们没有逐秒模拟,只靠「哨兵 + 每对相邻力定中间一段」一遍就推完了。
⚠️ 容易写错的地方
✗ 错：逐秒模拟整排同时倒
✓ 对：哨兵 + 相邻两力直接定中间一段
逐秒模拟每轮 O(n)、可能多轮,慢且难写对;相邻两力一次定一段,一遍线性
✗ 错：哨兵方向放反
✓ 对：左端放 L、右端放 R(朝外不影响内部)
哨兵要"朝外",左端 L 不会往右推、右端 R 不会往左推,才能既兜住边界又不干扰真实牌
✗ 错：R…L 正中那张乱填
✓ 对：区间长度为奇时正中两力抵消,保持直立 .
l 与 r 相遇在正中时左右距离相等、力抵消,填成 L 或 R 都错
完整代码（Python / C++ / Java）
Python
class Solution:
def pushDominoes(self, dominoes: str) -> str:
arr = list('L' + dominoes + 'R')
i = 0
for j in range(1, len(arr)):
if arr[j] == '.':
continue
if j - i > 1:
if arr[i] == arr[j]:
for k in range(i + 1, j):
arr[k] = arr[i]
elif arr[i] == 'R' and arr[j] == 'L':
l, r = i + 1, j - 1
while l < r:
arr[l], arr[r] = 'R', 'L'
l += 1
r -= 1
i = j
return ''.join(arr[1:-1])C++
#include <string>
using namespace std;
class Solution {
public:
string pushDominoes(string dominoes) {
string arr = "L" + dominoes + "R";
int i = 0;
for (int j = 1; j < (int)arr.size(); ++j) {
if (arr[j] == '.') continue;
if (j - i > 1) {
if (arr[i] == arr[j]) for (int k = i + 1; k < j; ++k) arr[k] = arr[i];
else if (arr[i] == 'R' && arr[j] == 'L') {
int l = i + 1, r = j - 1;
while (l < r) { arr[l++] = 'R'; arr[r--] = 'L'; }
}
}
i = j;
}
return arr.substr(1, arr.size() - 2);
}
};Java
import java.util.*;
class Solution {
public String pushDominoes(String dominoes) {
char[] arr = ("L" + dominoes + "R").toCharArray();
int i = 0;
for (int j = 1; j < arr.length; j++) {
if (arr[j] == '.') continue;
if (j - i > 1) {
if (arr[i] == arr[j]) for (int k = i + 1; k < j; k++) arr[k] = arr[i];
else if (arr[i] == 'R' && arr[j] == 'L') {
int l = i + 1, r = j - 1;
while (l < r) { arr[l++] = 'R'; arr[r--] = 'L'; }
}
}
i = j;
}
return new String(arr, 1, arr.length - 2);
}
}复杂度
时间
O(n)
指针 j 扫一遍;每张直立牌只在它所属的那一段里被填一次,合起来线性
空间
O(n)
把字符串复制成可改的字符数组(含两个哨兵),O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 推多米诺 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么加哨兵能简化代码?+
不加哨兵时,开头一段(第一个受力牌之前)和结尾一段(最后一个受力牌之后)要单独判断方向,容易写漏。左端加 L、右端加 R 后,这两段也变成普通的「相邻两力之间」情形,用同一套逻辑就能覆盖,代码更短更稳。
除了这套,还有别的解法吗?+
常见的还有「计算每张牌受到的净力」:从左到右记最近 R 的推力(随距离衰减)、从右到左记最近 L 的推力,两者相加,正倒右、负倒左、零保持直立。思路不同但同样 O(n),本题这套区间填充更直观。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 推多米诺 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。