LC 838. 推多米诺

题目描述

这是 LeetCode 上的 838. 推多米诺 ，难度为 中等。

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

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

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

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

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

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

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

示例 1：

1
2
3
4
5
输入：dominoes = "RR.L"

输出："RR.L"

解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：

1
2
3
输入：dominoes = ".L.R...LR..L.."

输出："LL.RR.LLRRLL.."

提示：

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

BFS

推倒骨牌是一个行为传递的过程，可以使用 BFS 来进行模拟。

起始将所有不为 . 的骨牌以 $(loc, time, dire)$ 三元组的形式进行入队，三元组所代表的含义为「位置为 $loc$ 的骨牌在 $time$ 时刻受到一个方向为 $dire$ 的力」，然后进行常规的 BFS 即可。

在受力（入队）时，我们尝试修改骨牌的状态，同时为了解决「一个骨牌同时受到左右推力时，维持站立状态不变」的问题，我们需要在尝试修改骨牌状态后，额外记录下该骨牌的状态修改时间，如果在同一时间内，一块骨牌受力两次（只能是来自左右两个方向的力），需要将该骨牌恢复成竖立状态。

代码：

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
class Solution {
    public String pushDominoes(String dominoes) {
        char[] cs = dominoes.toCharArray();
        int n = cs.length;
        int[] g = new int[n];
        Deque<int[]> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (cs[i] == '.') continue;
            int dire = cs[i] == 'L' ? -1 : 1;
            d.add(new int[]{i, 1, dire});
            g[i] = 1;
        }
        while (!d.isEmpty()) {
            int[] info = d.pollFirst();
            int loc = info[0], time = info[1], dire = info[2];
            int ne = loc + dire;
            if (cs[loc] == '.' || (ne < 0 || ne >= n)) continue;
            if (g[ne] == 0) { // 首次受力
                d.addLast(new int[]{ne, time + 1, dire});
                g[ne] = time + 1;
                cs[ne] = dire == -1 ? 'L' : 'R';
            } else if (g[ne] == time + 1) { // 多次受力
                cs[ne] = '.';
            }
        }
        return String.valueOf(cs);
    }
}

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

预处理 + 双指针

我们知道，如果一块原本竖立的骨牌最终倒下，必然是「受到来自左侧向右的力」或者「受到来自右侧向左的力」。

基于此，我们可以创建两个二维数组 l 和 r 分别存储每个位置 $i$ 的左侧和右侧的受力情况，每个的 $l[i]$ 和 $r[i]$ 分别存储「左侧」和「右侧」的最近受力点下标，以及该力的方向。

然后枚举所有 $dominoes[i]$ 为 . 的位置，获取其左侧的最近受力点 loc1 和受力方向 dire1，以及其右侧的最近受力点 loc2 和受力方向 dire2，并进行分情况讨论即可。

根据左右侧受力情况修改骨牌状态可通过「双指针」实现。

一些细节：为了避免每个样例都 new 大数组，可以使用 static 优化 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
class Solution {
    static int N = 100010;
    static int[][] l = new int[N][2], r = new int[N][2];
    public String pushDominoes(String dominoes) {
        char[] cs = dominoes.toCharArray();
        int n = cs.length;
        for (int i = 0, j = -1; i < n; i++) {
            if (cs[i] != '.') j = i;
            l[i] = new int[]{j, j != -1 ? cs[j] : '.'};
        }
        for (int i = n - 1, j = -1; i >= 0; i--) {
            if (cs[i] != '.') j = i;
            r[i] = new int[]{j, j != -1 ? cs[j] : '.'};
        }
        for (int i = 0; i < n; ) {
            if (cs[i] != '.' && ++i >= 0) continue;
            int j = i;
            while (j < n && cs[j] == '.') j++;
            j--;
            int[] a = l[i], b = r[j];
            int loc1 = a[0], dire1 = a[1], loc2 = b[0], dire2 = b[1];
            if (loc1 == -1 && loc2 == -1) { // 两侧无力
            } else if (loc1 == -1) { // 只有右侧有力，且力的方向向左
                if (dire2 == 'L') update(cs, i, j, 'L', 'L');
            } else if (loc2 == -1) { // 只有左侧有力，且力的方向向右
                if (dire1 == 'R') update(cs, i, j, 'R', 'R');
            } else { // 两侧有力，且两力方向「不同时」反向
                if (!(dire1 == 'L' && dire2 == 'R')) update(cs, i, j, (char)dire1, (char)dire2);
            }
            i = j + 1;
        }
        return String.valueOf(cs);
    }
    void update(char[] cs, int l, int r, char c1, char c2) {
        for (int p = l, q = r; p <= q; p++, q--) {
            if (p == q && c1 != c2) continue;
            cs[p] = c1; cs[q] = c2;
        }
    }
}

  • 时间复杂度：预处理 l 和 r 的复杂度为 $O(n)$；构造答案复杂度为 $O(n)$。整体复杂度为 $O(n)$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.838 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。