【算法文章10| 前缀和：力扣2055题：蜡烛之间的盘子】
题目链接：2055：蜡烛之间的盘子
这道题是力扣的一道1818分的题，大概题意是这样的：
- 给你一个字符串，字符串里面只有两种符号：字符
'*'和'|'，其中'*'表示 盘子 ，'|'表示 蜡烛 。 - 然后给你一个二维的查询数组
queries，对于每一个查询queries[i] = [lefti, righti],找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 - 返回一个整数数组
answer，其中answer[i]是第i个查询的答案。
总结一句话：找规定区间内， 在两支蜡烛之间的盘子的数目
这道题的难点在于，对于每一个查询区间[lefti, righti]，怎么找区间内的离边界最近的蜡烛的位置，也就是怎么寻找“有效边界”。
思路：寻找“有效边界”
- 定义前缀和sum[]，记录盘子的数量
- 定义两个数组left[] 跟 right[]，他们的含义如下：
- left[]表示：索引i左侧（含 i）最近的 ‘|’ (蜡烛) 的索引
- right[]表示：索引 i 右侧（含 i）最近的 ‘|’ (蜡烛) 的索引
- 枚举所有的查询
- 缩小区间范围
- 找左端点右边的第一根蜡烛，作为新的左端点
- 找右端点左边的第一根蜡烛，作为新的右端点
- 缩小区间范围
代码
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]（即前三个星号 ***）。
- 预处理的结果：
right数组：每一个位置向右看的第一根蜡烛都在索引 3。所以right[0] = 3。left数组：前三个位置向左看都没有蜡烛。所以left[0, 1, 2] = -1。
- 判断
if (l != -1 && r != -1 && l < r)- 这里
r是 -1，条件直接不成立。 - 结果：
ans[i] = 0。
场景二：只有一根蜡烛，或蜡烛在边缘无法包裹盘子
假设字符串 s = "***|**"，查询区间为 [0, 5]（整个字符串）。
- 预处理结果：
right[0]：从索引 0 开始向右找，第一根蜡烛在索引 3。所以l = 3。left[5]：从索引 5 开始向左找，第一根蜡烛也在索引 3。所以r = 3。
- 判断逻辑：
if (l < r)→ \rightarrow → 即if (3 < 3)。- 条件不成立（因为只有一根蜡烛，无法形成“中间”区域）。
- 结论：
ans[i] = 0。
场景三：区间内有蜡烛，但它们中间没盘子
假设字符串 s = "**||**"，查询区间为 [0, 5]。
- 预处理结果：
l = right[0]→ \rightarrow → 索引 2（第一根|）。r = left[5]→ \rightarrow → 索引 3（第二根|）。
- 前缀和计算：
sum[2]（前 2 个字符里的盘子数）是 2。sum[3]（前 3 个字符里的盘子数）也是 2（因为索引 2 是蜡烛，盘子数没增加）。
- 判断：
l < r(2 < 3) 成立。ans[i] = sum[3] - sum[2]→ \rightarrow →0。
如果对你有帮助，欢迎点赞、关注、收藏！
