Push Dominoes

838. 推多米诺

分析

字符串首尾哨兵添加：
- 为简化边界条件处理，在字符串首部添加 'L'，尾部添加 'R'，变成 dominoes = 'L' + dominoes + 'R'
- 这样首尾骨牌始终有确定的受力方向
预处理左右最近的受力源：
- 定义两个数组 l 和 r：
  - l[i] 表示索引 i 左侧最近的 'L' 的位置；
  - r[i] 表示索引 i 右侧最近的 'R' 的位置
- 遍历计算：
  - 从左向右遍历填充 l，记录每个位置最近的 'L'；
  - 从右向左遍历填充 r，记录每个位置最近的 'R'
根据受力平衡更新状态：
- 遍历每个位置，根据 l[i] 和 r[i] 的值判断受力方向：
  - 如果 dominoes[l[i]] == 'L' && dominoes[r[i]] == 'R'，受力平衡，骨牌保持竖立 '.'；
  - 如果两侧的受力方向一致，骨牌倒向对应方向；
  - 如果受力方向不同且距离不同，骨牌倒向距离近的一侧；
  - 如果受力方向不同且距离相等，骨牌保持竖立 '.'
移除哨兵：
- 返回字符串 dominoes.substr(1, n - 2)，移除首尾哨兵

时间复杂度

遍历三次字符串：分别计算 l 和 r 的值，以及最终更新 dominoes 的状态

总时间复杂度 O(n)

空间复杂度

空间复杂度：O(n)

C++代码

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


class Solution
{
public:
    string pushDominoes(string dominoes)
    {
      // 添加哨兵
      dominoes = 'L' + dominoes + 'R';
      int n = dominoes.size();
      std::vector<int> l(n), r(n);

      // 记录左侧最近的'L'
      int pos = 0;
      for (int i = 1; i < n; ++i)
      {
        if (dominoes[i] != '.')
          pos = i; // 更新最近的'L'或'R'
        l[i] = pos; // 保存当前位置左侧的最近受力源
      }

      // 记录右侧最近的'R'
      for (int i = n - 1; i >= 0; --i)
      {
        if (dominoes[i] != '.')
          pos = i; // 更新最近的'L'或'R'
        r[i] = pos; // 保存当前位置右侧的最近受力源
      }

      // 判断骨牌最终的状态
      for (int i = 0; i < n; ++i)
      {
        if (dominoes[l[i]] == 'L' && dominoes[r[i]] == 'R')
        {
          dominoes[i] = '.'; // 平衡受力
        }
        else if (dominoes[l[i]] == 'L' && dominoes[r[i]] == 'L')
        {
          dominoes[i] = 'L'; // 受左侧'L'影响
        }
        else if (dominoes[l[i]] == 'R' && dominoes[r[i]] == 'R')
        {
          dominoes[i] = 'R'; // 受右侧'R'影响
        }
        else
        {
          // 受不同方向影响，根据距离判断
          if (i - l[i] < r[i] - i)
            dominoes[i] = 'R';
          else if (i - l[i] > r[i] - i)
            dominoes[i] = 'L';
          else
            dominoes[i] = '.';
        }
      }

      // 移除首尾哨兵
      return dominoes.substr(1, n - 2);
    }
};