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

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

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

• 给你一个字符串，字符串里面只有两种符号：字符 '*' 和 '|' ，其中 '*' 表示 盘子 ，'|' 表示 蜡烛 。

• 然后给你一个二维的查询数组queries，对于每一个查询 queries[i] = [lefti, righti],找到 子字符串中 在 两支蜡烛之间 的盘子的 数目

• 返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

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

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

思路：寻找“有效边界”

代码

class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
int n = s.length();
//1.前缀和sum[]记录盘子的数量
int [] sum = new int[n+1];
//2.left[]统计索引i（含 i）左侧最近的'|'的索引
int []left = new int[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 = new int[n];
lastCandle = –1;
for(int i = n–1; i >= 0; i—) {
if(s.charAt(i) == '|') {
lastCandle = i;
}
right[i] = lastCandle;
}
int []ans = new int[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;
}
}

//找左端点右边的第一根蜡烛，作为新的左端点
int l = right[queries[i][0]];
//找右端点左边的第一根蜡烛，作为新的右端点
int r = left[queries[i][1]];

一定要理解这两句代码，这两句代码非常关键，我们的目的是：

• 将 left 向右移，找到区间内的第一根蜡烛。

  将 right 向左移，找到区间内的最后一根蜡烛。

• 时间复杂度：$O(n+q)$

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

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

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

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

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

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

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

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