题目

类型：数组

解题思路

对于任意一个查询 [a, b] 而言，需要统计所有左边和右边能够找到蜡烛的盘子数量。
一个自然的想法是：找到区间 [a, b] 两边缘的蜡烛，分别记为 c 和 d，显然区间 [c, d] 内的盘子都是需要被统计的。
因此，我们可以对字符串 s 进行从前往后的扫描，将所有的蜡烛下标添加到数组（数组严格递增），并预处理出盘子的「前缀和」数组。
然后处理询问时的「找区间 [a, b] 边缘蜡烛」操作可通过对数组「二分」来做，而「查询区间 [c, d] 内的盘子数量」操作可直接查询「前缀和」数组。
更进一步，在给定 s 的前提下，每个位置其左边和右边最近的蜡烛唯一确定。
我们可以在预处理前缀和的同时，预处理每个位置左右最近的蜡烛下标，从而省去每次二分。

代码解读：

对于每个查询 qs = [left, right] ：

首先要确定查询区间内位于最左侧和最右侧的蜡烛位置，即 left 右侧(包括 left) 最近的蜡烛位置，以及 right 左侧(包括 right) 最近的蜡烛位置。这里我们分别用两个辅助数组 l 和 r 来记录，其中，l[i] 表示在位置 i 左侧(包括 i )，离 i 最近的蜡烛的位置，r[i] 表示在位置 i 右侧(包括 i )，离 i 最近的蜡烛的位置。
然后，当我们找到查询区间内最左侧和最右侧的两个蜡烛的位置 l 和 r 之后，如果我们知道，在 l 和 r 之前分别有多少个盘子的话，那么在 l 和 r 之间的盘子个数（即查询区间内两个蜡烛之间的盘子个数）即为二者之差。这里我们使用第三个辅助数组 sum 来记录每个位置之前的盘子个数，即 sum[i] 表示在位置 i 之前的盘子个数。

最后，我们由 sum 得到查询区间最左侧蜡烛位置 l 和最右侧蜡烛位置 r 之前的盘子个数分别为 sum[l] 和 sum[r]，那么在 l 和 r 之间的盘子个数，即查询区间内两个蜡烛之间的盘子个数为 sum[r] - sum[l]。

代码

class Solution {
  public int[] platesBetweenCandles(String s, int[][] qs) {
      char[] cs = s.toCharArray();
      int n = cs.length, m = qs.length;
      // 离当前点最近的  左边蜡烛和右边蜡烛位置
      int[] l = new int[n], r = new int[n];
      // 计算前缀和数组 
      int[] sum = new int[n + 1];
      for (int i = 0, j = n - 1, p = -1, q = -1; i < n; i++, j--) {
          // 最近左边蜡烛点
          if (cs[i] == '|') p = i;
          // 最近右边蜡烛点
          if (cs[j] == '|') q = j;
          l[i] = p; r[j] = q;
          //更新前缀和
          sum[i + 1] = sum[i] + (cs[i] == '*' ? 1 : 0);
      }
      int[] ans = new int[m];
      for (int i = 0; i < m; i++) {
          int a = qs[i][0], b = qs[i][1];
          int c = r[a], d = l[b];
          // 左边蜡烛点小于右边蜡烛点位置
          if (c != -1 && c <= d) ans[i] = sum[d + 1] - sum[c];
      }
      return ans;
  }
}