「每日LeetCode」2022年2月21日

本文最后更新于：2023年3月19日 晚上

838.推多米诺

838.推多米诺

Category Difficulty Likes Dislikes
algorithms Medium (50.17%) 163 -

Tags
Companies
n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。
就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。
给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

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

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

示例 1：
输入：dominoes = “RR.L” 输出：“RR.L” 解释：第一张多米诺骨牌没有给第二张施加额外的力。
示例 2：
image.png
输入：dominoes = “.L.R…LR..L..” 输出：“LL.RR.LLRRLL..”
​

提示：

  • n == dominoes.length
  • 1 <= n <= 105
  • dominoes[i] 为 ‘L’、’R’ 或 ‘.’

思路

分别遍历两次，更新记录每个点离得最近的 L 和 R 的位置。再遍历一次，比较距离即可，若到达距离相等，那么保持直立。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
 * @lc app=leetcode.cn id=838 lang=javascript
 *
 * [838] 推多米诺
 */

// @lc code=start
/**
 * @param {string} dominoes
 * @return {string}
 */
var pushDominoes = function (dominoes) {
  const n = dominoes.length,
    arr = new Array(n).fill([Infinity, Infinity]);
  for (let i = 0, closeR = Infinity; i < dominoes.length; i++) {
    const element = dominoes[i];
    if (element === "R") {
      closeR = i;
    } else if (element === "L") {
      closeR = Infinity;
    }
    arr[i] = [arr[i][0], Math.abs(i - closeR)];
  }
  for (let i = dominoes.length - 1, closeL = Infinity; i >= 0; i--) {
    const element = dominoes[i];
    if (element === "L") {
      closeL = i;
    } else if (element === "R") {
      closeL = Infinity;
    }
    arr[i] = [Math.abs(closeL - i), arr[i][1]];
  }

  return arr
    .map(([L, R]) => {
      if (L === R) return ".";
      if (L > R) return "R";
      if (R > L) return "L";
    })
    .join("");
};
// @lc code=end