题目描述
思路解析动画文字版
记住:加哨兵 L…R,再看每对相邻受力牌之间那段怎么倒。下面一段段处理。
先在两端各加一张永不倒的哨兵牌:左边一个 L、右边一个 R(画面里灰色那两张)。有了它们,最左、最右那段也能套同一套规则,不用单独写边界。
扫描指针走到下标 2,这是个受力牌 L。它和上一个受力牌(下标 0 的 L)之间夹着 1 张直立牌,这一段怎么倒,就看这两端。
先看这一段:两端都是 L,中间这 1 张还直立着(灰色待定)。两端同向,接下来会被一起推倒。
两端是同一个方向 L,那中间这一整段都被往同一边推,全部填成 L(变绿落定)。
扫描指针走到下标 4,这是个受力牌 R。它和上一个受力牌(下标 2 的 L)之间夹着 1 张直立牌,这一段怎么倒,就看这两端。
先看这一段:左端是 L 往左倒、右端是 R 往右倒,两股力背对背走开。中间这 1 张被框住,接下来会确认它们原样不动。
确认一下:两股力背对背,中间这段没有任何人来推,所以原样保持直立 .。
扫描指针走到下标 8,这是个受力牌 L。它和上一个受力牌(下标 4 的 R)之间夹着 3 张直立牌,这一段怎么倒,就看这两端。
先看这一段:左端 R 往右推、右端 L 往左推,两股力对着挤。中间这 3 张会从最外一对开始、向中间一对对地落定。
从最外一对开始:第 5 位离左边的 R 近,倒成 R;第 7 位离右边的 L 近,倒成 L。再往里收一对。
收到正中间,只剩第 6 位。它离左边的 R 和右边的 L 一样远,两边力气相等、谁也推不动它,保持直立 .。
扫描指针走到下标 9,这是个受力牌 R。它和上一个受力牌(下标 8 的 L)之间夹着 0 张直立牌,这一段怎么倒,就看这两端。
这两个受力牌挨在一起,中间一张直立牌都没有,自然什么都不用做,直接看下一段。
扫描指针走到下标 11,这是个受力牌 L。它和上一个受力牌(下标 9 的 R)之间夹着 1 张直立牌,这一段怎么倒,就看这两端。
先看这一段:左端 R 往右推、右端 L 往左推,两股力对着挤。中间只有第 10 位这一张,它正好卡在两股力的中点,下一步就要判它受力抵消、保持直立。
收到正中间,只剩第 10 位。它离左边的 R 和右边的 L 一样远,两边力气相等、谁也推不动它,保持直立 .。
扫描指针走到下标 12,这是个受力牌 R。它和上一个受力牌(下标 11 的 L)之间夹着 0 张直立牌,这一段怎么倒,就看这两端。
这两个受力牌挨在一起,中间一张直立牌都没有,自然什么都不用做,直接看下一段。
所有相邻受力段都处理完了,回头整串看一遍:含两端哨兵在内,整排已经稳定下来,不会再有任何牌移动。下一步只剩去掉哨兵。
所有相邻受力段都处理完了。把两端的哨兵牌去掉,中间这串就是最终稳定状态 "LL.RR.LLR.L",和开头说的一致。回头看,我们没有逐秒模拟,只靠「哨兵 + 每对相邻力定中间一段」一遍就推完了。
边界:全直立 / 全同向 / R…L 正中抵消 / 单张,都被同一套规则覆盖。
两个高频追问:哨兵为何简化、净力法替代方案。
参考代码
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])复杂度
- 时间:O(n),指针 j 扫一遍;每张直立牌只在它所属的那一段里被填一次,合起来线性
- 空间:O(n),把字符串复制成可改的字符数组(含两个哨兵),O(n)
易错点
面试追问把动画讲成自己的话
追问为什么加哨兵能简化代码?
追问除了这套,还有别的解法吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
一手顺子
LeetCode 846 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题