题目

类型：双指针
image.png

解题思路

如果一块原本竖立的骨牌最终倒下，必然是「受到来自左侧向右的力」或者「受到来自右侧向左的力」。
基于此，可以创建两个二维数组 l 和 r 分别存储每个位置 i 的左侧和右侧的受力情况，每个的 l[i] 和 r[i] 分别存储「左侧」和「右侧」的最近受力点下标，以及该力的方向。
然后枚举所有 dominoes[i] 为 . 的位置，获取其左侧的最近受力点 loc1 和受力方向 dire1，以及其右侧的最近受力点 loc2 和受力方向 dire2，并进行分情况讨论即可。

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

代码

  1. class Solution {
  2.     static int N = 100010;
  3.     static int[][] l = new int[N][2], r = new int[N][2];
  4.     public String pushDominoes(String dominoes) {
  5.         char[] cs = dominoes.toCharArray();
  6.         int n = cs.length;
  7.         for (int i = 0, j = -1; i < n; i++) {
  8.             if (cs[i] != '.') j = i;
  9.             l[i] = new int[]{j, j != -1 ? cs[j] : '.'};
  10.         }
  11.         for (int i = n - 1, j = -1; i >= 0; i--) {
  12.             if (cs[i] != '.') j = i;
  13.             r[i] = new int[]{j, j != -1 ? cs[j] : '.'};
  14.         }
  15.         for (int i = 0; i < n; ) {
  16.             if (cs[i] != '.' && ++i >= 0) continue;
  17.             int j = i;
  18.             while (j < n && cs[j] == '.') j++;
  19.             j--;
  20.             int[] a = l[i], b = r[j];
  21.             int loc1 = a[0], dire1 = a[1], loc2 = b[0], dire2 = b[1];
  22.             if (loc1 == -1 && loc2 == -1) { // 两侧无力
  23.             } else if (loc1 == -1) { // 只有右侧有力，且力的方向向左
  24.                 if (dire2 == 'L') update(cs, i, j, 'L', 'L');
  25.             } else if (loc2 == -1) { // 只有左侧有力，且力的方向向右
  26.                 if (dire1 == 'R') update(cs, i, j, 'R', 'R');
  27.             } else { // 两侧有力，且两力方向「不同时」反向
  28.                 if (!(dire1 == 'L' && dire2 == 'R')) update(cs, i, j, (char)dire1, (char)dire2);
  29.             }
  30.             i = j + 1;
  31.         }
  32.         return String.valueOf(cs);
  33.     }
  34.     void update(char[] cs, int l, int r, char c1, char c2) {
  35.         for (int p = l, q = r; p <= q; p++, q--) {
  36.             if (p == q && c1 != c2) continue;
  37.             cs[p] = c1; cs[q] = c2;
  38.         }
  39.     }
  40. }