给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 ‘‘ 和 ‘|’ ，其中 ‘‘ 表示一个 盘子 ，’|’ 表示一支 蜡烛 。

    同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] 表示 子字符串 s[lefti…righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。

    比方说，s = “|||||“ ，查询 [3, 8] ，表示的是子字符串 “||**|” 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。
    请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

    示例 1:

    输入：s = “||*|”, queries = [[2,5],[5,9]]
    输出：[2,3]
    解释：

    • queries[0] 有两个盘子在蜡烛之间。
    • queries[1] 有三个盘子在蜡烛之间。
      示例 2:

    输入：s = “||||||*”, queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
    输出：[9,0,0,0,0]
    解释：

    • queries[0] 有 9 个盘子在蜡烛之间。
    • 另一个查询没有盘子在蜡烛之间。

    提示：

    3 <= s.length <= 105
    s 只包含字符 ‘*’ 和 ‘|’ 。
    1 <= queries.length <= 105
    queries[i].length == 2
    0 <= lefti <= righti < s.length

    1. class Solution {
    2.     public int[] platesBetweenCandles(String s, int[][] queries) {
    3.         char[] ch = s.toCharArray();
    4.         int n = ch.length;
    5.         //存储蜡烛的下标
    6.         List<Integer> list = new ArrayList<>();
    7.         for (int i = 0; i < n; ++i) 
    8.             if (ch[i] == '|') list.add(i);
    9.         int len = queries.length;
    10.         int size = list.size();
    11.         int[] res = new int[len];
    12.         //没有蜡烛
    13.         if (size == 0) {
    14.             for (int i = 0; i < len; ++i) res[i] = 0;
    15.             return res;
    16.         }
    17.         for (int i = 0; i < len; ++i) {
    18.             int a = queries[i][0], b = queries[i][1];
    19.             //找到第一个大于等于a的蜡烛下标
    20.             int l = 0, r = size - 1;
    21.             while (l < r) {
    22.                 int mid = l + r >> 1;
    23.                 if (list.get(mid) >= a) r = mid;
    24.                 else l = mid + 1;
    25.             }
    26.             int tl = l;
    27.             l = 0; r = size - 1;
    28.             //找到第一个小于等于b的蜡烛下标
    29.             while (l < r) {
    30.                 int mid = l + r + 1 >> 1;
    31.                 if (list.get(mid) <= b) l = mid;
    32.                 else r = mid - 1;
    33.             }
    34.             int tr = l;
    35.             //如果tl >= tr说明之间没有蜡烛区间
    36.             if (tl < tr) {
    37.                 res[i] = list.get(tr) - list.get(tl) + 1 - (tr - tl +1);
    38.             } else res[i] = 0;
    39.         }
    40.         return res;
    41.     }
    42. }

    也可以通过前缀和处理每个位置的前后蜡烛下标