[LeetCode] 每日一题 838. 推多米诺（条件归类）

题目描述

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

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

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

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

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

• dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，

• dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，

• dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。

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

题目链接

https://leetcode.cn/problems/push-dominoes

示例输入

示例 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' 或 '.'

解题思路

这道题一开始看起来就像模拟题，但如果直接按秒模拟推导，会非常混乱。因此我一开始的实现也比较零散、复杂，效果并不好。后来参考了一个非常清晰的解法：将问题简化为区间条件处理，并分为四种情况进行判断处理：

1. L...L：中间全部变成 L；

2. R...R：中间全部变成 R；

3. R...L：前一半变成 R，后一半变成 L，中间如果有奇数个点，最中间那个保持不变；

4. L...R：中间不受力，保持原样。

为了让这些判断更统一，我们可以在原字符串前加一个 L，后加一个 R，构建虚拟边界，就像链表里常见的“虚拟头结点”技巧一样，这样就不用为边界特判了，判断逻辑也更加统一简洁。

代码实现

class Solution {
    public String pushDominoes(String dominoes) {
        char[] dominoesArray = ("L" + dominoes + "R").toCharArray();
        int pre = 0;
        for (int i = 1; i < dominoesArray.length; i++) {
            if (dominoesArray[i] == '.') {
                continue;
            }
            if (dominoesArray[i] == dominoesArray[pre]) {
                Arrays.fill(dominoesArray, pre + 1, i, dominoesArray[i]);
            } else if (dominoesArray[i] == 'L') {
                Arrays.fill(dominoesArray, pre + 1, (pre + i + 1) / 2, 'R');
                Arrays.fill(dominoesArray, (pre + i) / 2 + 1, i, 'L');
            }
            pre = i;
        }
        return new String(dominoesArray, 1, dominoesArray.length - 2);
    }
}

复杂度分析

• 时间复杂度：O(n)
  只需一次遍历加若干次数组填充操作，整体是线性时间；

• 空间复杂度：O(n)
  因为我们构造了一个额外的字符数组（添加了两端虚拟节点），空间复杂度也是线性级别。

总结

这道题是典型的“条件归类 + 避免边界特判”的处理技巧，虽然不是一眼能看出思路的模拟题，但一旦归纳出规律并构建统一模型，写起来就非常清晰。在遇到这类物理模型推导题时，我们可以多想想能不能“虚构边界”或“将情况标准化”，从而减少逻辑分支，提升代码的可维护性。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。