一、题目描述
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 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 <= 105s只包含字符'*'和'|'。1 <= queries.length <= 105queries[i].length == 20 <= lefti <= righti < s.length
二、思路分析
看到这个题，我们第一反应就是这个是在求解区域和。想要求解区域和，那么我们就需要知道这段区域的左边界和右边界。
但是题目中，稍微提高了一丢丢丢的难度，这里边界并不是直接给出来的，而是需要去查找，题目中使用蜡烛表示边界， 也就会出现一种情况，选中的这段区域可能没有蜡烛或者只有一个蜡烛
接下来，我们先看看暴力怎么解决这个问题呢
首先是拿到区域的范围后，我们可以遍历这段区域，计算这段区域中的盘子数量，从左往右开始遍历，我们使用变量ans保存这段区域的盘子数量，使用变量count计算当前统计的盘子数量。当遇到第一个蜡烛的时候，我们开始计数，当后面再遇到蜡烛时，我们就更新ans变量的值。最后我们返回ans变量的值。
示例代码
class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
int[] result = new int[queries.length];
for (int k = 0; k < queries.length; ++k) {
int[] query = queries[k];
// 记录当前区域，两边有蜡烛的盘子数量
int ans = 0;
// 对盘子的数量进行计数，遇到蜡烛的时候更新ans的值
int count = 0;
// 标记是不是第一次遇到盘子，为true的时候count开始计数
boolean first = false;
// 遍历指定区域内的字符
for (int i = query[0]; i <= query[1]; ++i) {
// 如果是蜡烛，则更新当前区域的盘子的最大数量
if (s.charAt(i) == '|') {
ans = Math.max(ans, count);
first = true;
}
// 如果标记为true，且当前字符为*时，开始计数
if (first && s.charAt(i) == '*') {
++count;
}
}
// 盘子数量放到结果集合
result[k] = ans;
}
return result;
}
}复杂度分析
- 时间复杂度：
O(n * m)，n 表示询问中区域的平均长度，m 表示询问的次数 - 空间复杂度：
O(1)
我们可以看出来，这个时间复杂度还是很恐怖的，那么是不是还有更加优雅的方法呢？
假如我们把蜡烛全部换成盘子，这题改成查询指定区域内的盘子数量，那么这题就变成了查询区间的数字之和，这时候就可以考虑使用前缀和的方法求解。
接着是加上蜡烛，那么就要定位区域内符合题目要求的两根蜡烛的位置：离左边界最近的那个蜡烛和离右边界最近的那根蜡烛
我们可以提前做处理，记录下每个位置，离它最近的右边和左边的蜡烛的位置。
当给出区域的时候，我们直接获取到蜡烛位置，然后计算两个蜡烛的区间和即可。
这里也有一些需要注意的点，例如盘子左侧没有蜡烛时，我们怎么表示左侧最近的蜡烛的位置。区域内蜡烛不足两根时的场景。
示例代码
class Solution1 {
public int[] platesBetweenCandles(String s, int[][] queries) {
// 获取字符串长度
int n = s.length();
// 统计字符串中盘子的前缀和
int[] preSum = new int[n + 1];
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
// 如果是盘子则数量+1，如果是蜡烛则数量不变
preSum[i + 1] = c == '*' ? preSum[i] + 1 : preSum[i];
}
// 计算当前盘子左边最近的蜡烛在哪个位置，左边没有蜡烛时用-1表示
int[] left = new int[n];
int l = -1;
for (int i = 0; i < n; i++) {
// 如果当前位置是蜡烛，则更新左侧最近蜡烛的位置
if (s.charAt(i) == '|') {
l = i;
}
left[i] = l;
}
// 计算当前盘子右侧最近蜡烛的在哪个位置，右侧没有蜡烛时用-1表示
int[] right = new int[n];
int r = -1;
for (int i = n - 1; i >= 0; i--) {
// 如果当前位置是蜡烛，则更新右侧最近蜡烛的位置
if (s.charAt(i) == '|') {
r = i;
}
right[i] = r;
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int[] query = queries[i];
// 获取区域内左侧蜡烛的位置，在左边界的右边
int lIndex = right[query[0]];
// 获取区域内右侧蜡烛的位置，在右边界的左边
int rIndex = left[query[1]];
// 如果蜡烛数量不够，则为0
if (lIndex == -1 || lIndex >= rIndex) {
ans[i] = 0;
} else {
ans[i] = preSum[rIndex] - preSum[lIndex];
}
}
return ans;
}
}复杂度分析
- 时间复杂度：
O(n + m)，n 表示字符串的长度，预处理的遍历字符，m 表示查询的次数。 - 空间复杂度：
O(n)，n 表示字符串的长度，需要数组保存字符串的每个位置上的盘子数量以及左右的最近蜡烛位置
三、总结
当遇到一个题的时候，我们可以先看看暴力能不能解决，然后在暴力的基础上做优化，暴力求解释，重复求解的部分可以考虑使用缓存记录一下。区间和相关的问题，可以优先考虑使用前缀和的方法求解。
标签：2055,int,ans,LeetCode,queries,字符串,蜡烛,盘子 From： https://blog.51cto.com/u_15812995/9063837