0838. 推多米诺【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 力场模拟

1. 📝 题目描述

• leetcode

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

• dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
• dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
• dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。

返回表示最终状态的字符串。

---

示例 1：

输入：dominoes = "RR.L"
输出："RR.L"
解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：

输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

---

提示：

• n == dominoes.length
• 1 <= n <= 10^5
• dominoes[i] 为 'L'、'R' 或 '.'

2. 🎯 s.1 - 力场模拟

c

char* pushDominoes(char* dominoes) {
    int n = strlen(dominoes);
    int* forces = (int*)calloc(n, sizeof(int));
    int f = 0;
    for (int i = 0; i < n; i++) {
        if (dominoes[i] == 'R') f = n;
        else if (dominoes[i] == 'L') f = 0;
        else f = f > 0 ? f - 1 : 0;
        forces[i] += f;
    }
    f = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (dominoes[i] == 'L') f = n;
        else if (dominoes[i] == 'R') f = 0;
        else f = f > 0 ? f - 1 : 0;
        forces[i] -= f;
    }
    char* res = (char*)malloc(n + 1);
    for (int i = 0; i < n; i++)
        res[i] = forces[i] > 0 ? 'R' : forces[i] < 0 ? 'L' : '.';
    res[n] = '\0';
    free(forces);
    return res;
}

js

/**
 * @param {string} dominoes
 * @return {string}
 */
var pushDominoes = function (dominoes) {
  const n = dominoes.length
  const forces = new Array(n).fill(0)
  let f = 0
  for (let i = 0; i < n; i++) {
    if (dominoes[i] === 'R') f = n
    else if (dominoes[i] === 'L') f = 0
    else f = Math.max(f - 1, 0)
    forces[i] += f
  }
  f = 0
  for (let i = n - 1; i >= 0; i--) {
    if (dominoes[i] === 'L') f = n
    else if (dominoes[i] === 'R') f = 0
    else f = Math.max(f - 1, 0)
    forces[i] -= f
  }
  const res = []
  for (let i = 0; i < n; i++) {
    if (forces[i] > 0) res.push('R')
    else if (forces[i] < 0) res.push('L')
    else res.push('.')
  }
  return res.join('')
}

py

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        forces = [0] * n
        f = 0
        for i in range(n):
            if dominoes[i] == 'R': f = n
            elif dominoes[i] == 'L': f = 0
            else: f = max(f - 1, 0)
            forces[i] += f
        f = 0
        for i in range(n - 1, -1, -1):
            if dominoes[i] == 'L': f = n
            elif dominoes[i] == 'R': f = 0
            else: f = max(f - 1, 0)
            forces[i] -= f
        return ''.join('R' if f > 0 else 'L' if f < 0 else '.' for f in forces)

• 时间复杂度：$O(n)$，其中 n 是多米诺骨牌数量
• 空间复杂度：$O(n)$

算法思路：

• 从左向右计算 R 的推力（逾减），从右向左计算 L 的推力
• 合并两个方向的力，正为 R、负为 L、零为站立