接上文本篇文章我们来讲讲解决方案。方法一广度优先搜索当时间为 0 时部分骨牌会受到一个初始的向左或向右的力而翻倒。过了 1 秒后这些翻倒的骨牌会对其周围的骨牌施加一个力。具体表现为向左翻倒的骨牌如果它有直立的左边紧邻的骨牌则会对该直立的骨牌施加一个向左的力。向右翻倒的骨牌如果它有直立的右边紧邻的骨牌则会对该直立的骨牌施加一个向右的力。接下去需要分析这些 1 秒时受力的骨牌的状态。如果仅受到单侧的力它们会倒向单侧如果受到两个力则会保持平衡。再过 1秒后这些新翻倒的骨牌又会对其他直立的骨牌施加力而不会对正在翻倒或已经翻倒的骨牌施加力。这样的思路类似于广度优先搜索。我们用一个队列 q 模拟搜索的顺序数组 time 记录骨牌翻倒或者确定不翻倒的时间翻倒的骨牌不会对正在翻倒或者已经翻倒的骨牌施加力数组 force 记录骨牌受到的力骨牌仅在受到单侧的力时会翻倒。代码Python3class Solution: def pushDominoes(self, dominoes: str) - str: n len(dominoes) q deque() time [-1] * n force [[] for _ in range(n)] for i, f in enumerate(dominoes): if f ! .: q.append(i) time[i] 0 force[i].append(f) res [.] * n while q: i q.popleft() if len(force[i]) 1: res[i] f force[i][0] ni i - 1 if f L else i 1 if 0 ni n: t time[i] if time[ni] -1: q.append(ni) time[ni] t 1 force[ni].append(f) elif time[ni] t 1: force[ni].append(f) return .join(res)Javaclass Solution { public String pushDominoes(String dominoes) { int n dominoes.length(); DequeInteger queue new ArrayDequeInteger(); int[] time new int[n]; Arrays.fill(time, -1); ListCharacter[] force new List[n]; for (int i 0; i n; i) { force[i] new ArrayListCharacter(); } for (int i 0; i n; i) { char f dominoes.charAt(i); if (f ! .) { queue.offer(i); time[i] 0; force[i].add(f); } } char[] res new char[n]; Arrays.fill(res, .); while (!queue.isEmpty()) { int i queue.poll(); if (force[i].size() 1) { char f force[i].get(0); res[i] f; int ni f L ? i - 1 : i 1; if (ni 0 ni n) { int t time[i]; if (time[ni] -1) { queue.offer(ni); time[ni] t 1; force[ni].add(f); } else if (time[ni] t 1) { force[ni].add(f); } } } } return new String(res); } }C#public class Solution { public string PushDominoes(string dominoes) { int n dominoes.Length; Queueint queue new Queueint(); int[] time new int[n]; Array.Fill(time, -1); IListchar[] force new IListchar[n]; for (int i 0; i n; i) { force[i] new Listchar(); } for (int i 0; i n; i) { char f dominoes[i]; if (f ! .) { queue.Enqueue(i); time[i] 0; force[i].Add(f); } } char[] res new char[n]; Array.Fill(res, .); while (queue.Count 0) { int i queue.Dequeue(); if (force[i].Count 1) { char f force[i][0]; res[i] f; int ni f L ? i - 1 : i 1; if (ni 0 ni n) { int t time[i]; if (time[ni] -1) { queue.Enqueue(ni); time[ni] t 1; force[ni].Add(f); } else if (time[ni] t 1) { force[ni].Add(f); } } } } return new string(res); } }复杂度分析时间复杂度O(n)其中 n 是 dominoes 的长度。每个下标会最多被判断一次状态。空间复杂度O(n)。队列和数组最多各包含 n 个元素。