解題說明
Push Dominoes
題目描述：一排骨牌用字串表示，L 向左倒，R 向右倒，. 為直立。每秒鐘，被推的骨牌會推倒相鄰的直立骨牌。若一個骨牌同時受到左右推力則保持直立。求最終的骨牌狀態。
解題思路：使用力的模擬法。為每個位置計算受到的「向右力」和「向左力」：
- 向右掃描：從左到右，遇到
R時力量最大（設為 n），之後每格遞減。遇到L時力量歸零。 - 向左掃描：從右到左，遇到
L時力量最大（設為 n），之後每格遞減。遇到R時力量歸零。 - 對每個位置比較右力和左力：右力大則為
R，左力大則為L，相等則為.。
C++ 解法
複雜度分析
時間複雜度：O(n) — 三次線性掃描。
空間複雜度：O(n) — force 陣列。
虛擬碼
1. Create force array of size n, initialized to 0 2. Left-to-right scan (right force): - If 'R': f = n - If 'L': f = 0 - Else: f = max(f-1, 0) - force[i] += f 3. Right-to-left scan (left force): - If 'L': f = n - If 'R': f = 0 - Else: f = max(f-1, 0) - force[i] -= f 4. For each i: - force[i] > 0 → 'R', force[i] < 0 → 'L', else '.'
其他解法
雙指標法：找出相鄰的 L/R 片段邊界，對每個片段獨立處理。R...L 片段從兩端向中間填充；L...R 片段中間保持不變；R...R 全部向右；L...L 全部向左。時間 O(n)，空間 O(1)（原地修改）。
BFS 模擬：將所有初始推力的位置放入佇列，模擬每一秒的傳播。時間 O(n)，空間 O(n)。更直觀地模擬物理過程。
延伸思考
- 力的模擬法中，為什麼用 n 作為初始力量（而非無窮大）就足夠了？
- 雙指標法如何處理字串開頭和結尾沒有
L/R的情況？ - 如果骨牌可以向上下左右四個方向倒（二維骨牌），問題會如何變化？