838. 推多米诺

题目描述

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

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

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

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

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

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

示例 1:

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

示例 2:

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

提示:

$$
\begin{align}
&n == dominoes.length\\
&1 \le n \le 10^5\\
&dominoes[i] \in \{L, R, .\}\\
\end{align}
$$

当时间为 $0$ 时, 部分骨牌会受到一个初始的向左或向右的力而翻倒. 过了 $1$ 秒后, 这些翻倒的骨牌会对其周围的骨牌施加一个力. 具体表现为:

接下去需要分析这些 $1$ 秒时受力的骨牌的状态. 如果仅受到单侧的力, 它们会倒向单侧; 如果受到两个力, 则会保持平衡. 再过 $1$ 秒后, 这些新翻倒的骨牌又会对其他直立的骨牌施加力, 而不会对正在翻倒或已经翻倒的骨牌施加力.

这样的思路类似于广度优先搜索. 我们用一个队列 $q$ 模拟搜索的顺序; 数组 $\textit{time}$ 记录骨牌翻倒或者确定不翻倒的时间, 翻倒的骨牌不会对正在翻倒或者已经翻倒的骨牌施加力; 数组 $\textit{force}$ 记录骨牌受到的力, 骨牌仅在受到单侧的力时会翻倒.

我们可以枚举所有连续的没有被推动的骨牌，根据这段骨牌的两边骨牌（如果有的话）的推倒方向决定这段骨牌的最终状态：

特别地，如果左侧没有被推倒的骨牌，则假设存在一块向左倒的骨牌；如果右侧没有被推倒的骨牌，则假设存在一块向右倒的骨牌。这样的假设不会破坏骨牌的最终状态，并且边界情况也可以落入到上述三种情况中。

我们可以使用两个指针 $i$ 和 $j$ 来枚举所有连续的没有被推动的骨牌，$\textit{left}$ 和 $\textit{right}$ 表示两边骨牌的推倒方向。根据上述三种情况来计算骨牌的最终状态。

R 为（，L 为），转换为寻找有效括号问题。

首先，用栈，以存储（位置。

过程是遇到（入栈，遇到）出栈，说明（）匹配，如果栈空，说明有）为匹配。

剩栈，说明有（未匹配。

各情况处理：