蜡烛之间的盘子数量怎么用前缀和和最近蜡烛预处理？

简化版

查询某个区间内被两根蜡烛夹住的盘子数量，可以预处理。

用前缀和统计盘子数量，再预处理每个位置左侧最近蜡烛和右侧最近蜡烛。

对查询 [l, r]，找到区间内最左蜡烛 leftCandle 和最右蜡烛 rightCandle，如果两者存在且 leftCandle < rightCandle，答案就是中间盘子前缀和差值。

详细版

字符串由 '*' 和 '|' 组成，盘子只有在两根蜡烛之间才被计入。

预处理三类数组：

prefixPlate[i]：前 i 个字符中的盘子数量；
nearestRight[i]：从 i 往右最近的蜡烛位置；
nearestLeft[i]：从 i 往左最近的蜡烛位置。

查询 [l, r] 时：

a = nearestRight[l]
b = nearestLeft[r]

如果 a < b，答案是 prefixPlate[b] - prefixPlate[a + 1] 或按定义写成两根蜡烛之间的盘子数。每次查询 O(1)。

完整版教学

一、为什么只用盘子前缀和还不够

普通前缀和能快速算区间里有多少盘子，但本题要求盘子必须夹在两根蜡烛之间。查询 [l, r] 里的边缘盘子如果外侧没有蜡烛，就不能计入。因此除了盘子数量，还要快速找到区间内有效的左右边界蜡烛。

易错点：区间里的盘子不一定都算，只有最左蜡烛和最右蜡烛之间的盘子才算。

二、三个预处理数组分别解决什么

prefixPlate 解决“某段有多少盘子”；nearestRight 解决“从查询左端开始，第一根蜡烛在哪”；nearestLeft 解决“从查询右端开始，最后一根蜡烛在哪”。这三个信息合起来，才能在 O(1) 回答一个查询。

数组	方向	作用
`prefixPlate`	左到右	快速求盘子数
`nearestRight`	右到左预处理	找左边界内第一根蜡烛
`nearestLeft`	左到右预处理	找右边界内最后一根蜡烛

多次查询时，这种预处理非常划算。

三、带数字推演

字符串 s = "**|**|***|"，查询 [0, 8]。

区间内最左蜡烛在 2
区间内最右蜡烛在 5
两根蜡烛之间是位置 3,4，两块盘子

位置 0,1 的盘子在最左蜡烛外，不计入；位置 6,7,8 如果右侧蜡烛不在查询内，也不计入。

四、代码模板

实现如下：

function platesBetweenCandles(s, queries) {
  const n = s.length
  const prefix = new Array(n + 1).fill(0)
  const left = new Array(n).fill(-1)
  const right = new Array(n).fill(-1)

  let last = -1
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + (s[i] === '*' ? 1 : 0)
    if (s[i] === '|') last = i
    left[i] = last
  }

  last = -1
  for (let i = n - 1; i >= 0; i--) {
    if (s[i] === '|') last = i
    right[i] = last
  }

  return queries.map(([l, r]) => {
    const a = right[l]
    const b = left[r]
    if (a === -1 || b === -1 || a >= b) return 0
    return prefix[b] - prefix[a + 1]
  })
}

prefix[b] - prefix[a + 1] 表示开区间 (a, b) 中的盘子数。

五、为什么查询是 O(1)

每个查询只做常数次数组访问和一次前缀差值。预处理是 O(n)，如果有 q 个查询，总复杂度是 O(n + q)。如果每次查询都在区间内扫描找蜡烛，最坏会变成 O(nq)。

预处理一次：prefix + nearest arrays
每次查询：找 a、b、做差

这正是前缀和适合多查询问题的原因。

六、常见误区与追问

误区：直接返回区间盘子总数。 没被两根蜡烛夹住的盘子不能算。
误区：找错最近蜡烛方向。 左端要找右侧最近蜡烛，右端要找左侧最近蜡烛。
误区：前缀差值把蜡烛位置算进去。 盘子只在两根蜡烛之间，通常用开区间。
追问：为什么不每次二分蜡烛位置？ 可以预存所有蜡烛下标再二分，复杂度 O(q log n)；最近数组能做到 O(q)。
追问：没有两根蜡烛怎么办？ 返回 0，因为不存在被夹住的盘子。

这些点考的是“区间有效边界”和“前缀计数”的结合。

七、加强记忆

蜡烛盘子题记成“三件套”：盘子前缀和、左侧最近蜡烛、右侧最近蜡烛。查询时先把 [l,r] 收缩到区间内第一根和最后一根蜡烛，再用前缀和算两根蜡烛之间的盘子。不要把边缘没被夹住的盘子算进去。

简化版

详细版