【算法文章10| 前缀和：力扣2055题：蜡烛之间的盘子】

题目链接：2055：蜡烛之间的盘子

这道题是力扣的一道1818分的题，大概题意是这样的：

• 给你一个字符串，字符串里面只有两种符号：字符 '*' 和 '|' ，其中 '*' 表示 盘子 ，'|' 表示 蜡烛 。
• 然后给你一个二维的查询数组queries，对于每一个查询 queries[i] = [lefti, righti],找到 子字符串中 在 两支蜡烛之间 的盘子的 数目
• 返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

总结一句话：找规定区间内， 在两支蜡烛之间的盘子的数目

这道题的难点在于，对于每一个查询区间[lefti, righti]，怎么找区间内的离边界最近的蜡烛的位置，也就是怎么寻找“有效边界”。

思路：寻找“有效边界”

1. 定义前缀和sum[]，记录盘子的数量
2. 定义两个数组left[] 跟 right[]，他们的含义如下：
   1. left[]表示：索引i左侧（含 i）最近的 ‘|’ (蜡烛) 的索引
   2. right[]表示：索引 i 右侧（含 i）最近的 ‘|’ (蜡烛) 的索引
3. 枚举所有的查询
   • 缩小区间范围
     • 找左端点右边的第一根蜡烛，作为新的左端点
     • 找右端点左边的第一根蜡烛，作为新的右端点

代码

classSolution{publicint[]platesBetweenCandles(String s,int[][] queries){int n = s.length();//1.前缀和sum[]记录盘子的数量int[] sum =newint[n+1];//2.left[]统计索引i（含 i）左侧最近的'|'的索引int[]left =newint[n];int lastCandle =-1;for(int i =0; i < n; i++){if(s.charAt(i)=='|'){ sum[i+1]= sum[i]; lastCandle = i;}else{ sum[i+1]= sum[i]+1;} left[i]= lastCandle;}//3.right[]统计索引i（含 i）右侧最近的'|'的索引int[]right =newint[n]; lastCandle =-1;for(int i = n-1; i >=0; i--){if(s.charAt(i)=='|'){ lastCandle = i;} right[i]= lastCandle;}int[]ans =newint[queries.length];for(int i =0; i < queries.length; i++){//找左端点右边的第一根蜡烛，作为新的左端点int l = right[queries[i][0]];//找右端点左边的第一根蜡烛，作为新的右端点int r = left[queries[i][1]];//更新答案if(l !=-1&& r !=-1&& l < r){ ans[i]= sum[r]- sum[l];}else{ ans[i]=0;}}return ans;}}

一定要理解这两句代码，这两句代码非常关键，我们的目的是：将 left 向右移，找到区间内的第一根蜡烛。将 right 向左移，找到区间内的最后一根蜡烛。

• 时间复杂度： O ( n + q ) O(n + q) O(n+q)
  • 遍历字符串计算前缀和 sum 和 left 数组：O(n)
  • 遍历字符串计算 right 数组：O(n)
  • 遍历查询数组 queries：O(q)（q = queries.length）

利用具体案例帮助理解代码

场景一：区间内完全没有蜡烛

假设字符串 s = "***|***"，长度为 7。查询区间为 [0, 2]（即前三个星号 ***）。

1. 预处理的结果：
   • right 数组：每一个位置向右看的第一根蜡烛都在索引 3。所以 right[0] = 3。
   • left 数组：前三个位置向左看都没有蜡烛。所以 left[0, 1, 2] = -1。
2. 判断
   • if (l != -1 && r != -1 && l < r)
   • 这里 r 是 -1，条件直接不成立。
   • 结果：ans[i] = 0。

场景二：只有一根蜡烛，或蜡烛在边缘无法包裹盘子

假设字符串 s = "***|**"，查询区间为 [0, 5]（整个字符串）。

1. 预处理结果：
   • right[0]：从索引 0 开始向右找，第一根蜡烛在索引 3。所以 l = 3。
   • left[5]：从索引 5 开始向左找，第一根蜡烛也在索引 3。所以 r = 3。
2. 判断逻辑：
   • if (l < r) → \rightarrow → 即 if (3 < 3)。
   • 条件不成立（因为只有一根蜡烛，无法形成“中间”区域）。
   • 结论：ans[i] = 0。

场景三：区间内有蜡烛，但它们中间没盘子

假设字符串 s = "**||**"，查询区间为 [0, 5]。

1. 预处理结果：
   • l = right[0] → \rightarrow → 索引 2（第一根 |）。
   • r = left[5] → \rightarrow → 索引 3（第二根 |）。
2. 前缀和计算：
   • sum[2]（前 2 个字符里的盘子数）是 2。
   • sum[3]（前 3 个字符里的盘子数）也是 2（因为索引 2 是蜡烛，盘子数没增加）。
3. 判断：
   • l < r (2 < 3) 成立。
   • ans[i] = sum[3] - sum[2] → \rightarrow →0。

如果对你有帮助，欢迎点赞、关注、收藏！