2055. 蜡烛之间的盘子 Medium
给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 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 个盘子在蜡烛之间。
另一个查询没有盘子在蜡烛之间。
解题思路
输入： 一个表示 桌子(*) 蜡烛(|) 的字符串 s，一个二维数组 queries
输出： 返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
本题属于一维前缀和问题。
- 我们可以先将每个 桌子(*) 的前缀和求出
prefixSum - 再将从左侧开始最靠近 蜡烛(|) 的位置整理出来
leftCandle - 再将从右侧开始最靠近 蜡烛(|) 的位置整理出来
rightCandle - 对于每个
query，用两根最靠近边界的蜡烛来圈定范围 - 左边界就是从右侧开始计算最靠近当前位置的蜡烛
rightCandle[i] - 右边界就是从左侧开始计算最靠近当前位置的蜡烛
leftCandle[i] - 计算两个蜡烛之间的 '*' 数量即可
代码实现
from typing import List
class Solution:
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
# prefixSum[i] 表示前 i 个字符中 '*' 的数量（不含 i）
prefixSum = [0] * (n + 1)
# leftCandle[i] 表示从左到当前位置 i 为止，最靠近的蜡烛（|）的位置
leftCandle = [-1] * n
# rightCandle[i] 表示从右到当前位置 i 为止，最靠近的蜡烛（|）的位置
rightCandle = [-1] * n
# 构建 prefixSum 前缀和数组
for i in range(n):
if s[i] == '*':
prefixSum[i + 1] = prefixSum[i] + 1 # 如果是盘子，数量加1
else:
prefixSum[i + 1] = prefixSum[i] # 如果是蜡烛，数量不变
# 构建 leftCandle 数组
lastCandle = -1 # 记录上一个蜡烛的位置
for i in range(n):
if s[i] == '|':
lastCandle = i
leftCandle[i] = lastCandle
# 构建 rightCandle 数组
lastCandle = -1 # 重新从右往左扫
for i in range(n - 1, -1, -1):
if s[i] == '|':
lastCandle = i
rightCandle[i] = lastCandle
result = []
# 遍历每个查询
for start, end in queries:
l = rightCandle[start] # 找到从 start 开始向右的第一个蜡烛
r = leftCandle[end] # 找到从 end 开始向左的第一个蜡烛
# 如果找到的左右蜡烛位置合法，并且左边在右边之前
if l != -1 and r != -1 and l < r:
# 计算蜡烛之间的盘子数量（用前缀和差值）
result.append(prefixSum[r] - prefixSum[l])
else:
# 无效的范围，返回 0
result.append(0)
return result/**
* @param {string} s
* @param {number[][]} queries
* @return {number[]}
*/
var platesBetweenCandles = function(s, queries) {
const prefixSum = Array(s.length + 1).fill(0);
const leftCandle = Array(s.length).fill(-1);
const rightCandle = Array(s.length).fill(-1);
for (let i = 0; i < s.length; i++) {
prefixSum[i + 1] = s[i] === '*' ? prefixSum[i] + 1 : prefixSum[i];
}
let lastCandle = -1;
for (let i = 0; i < s.length; i++) {
if (s[i] === '|') lastCandle = i;
leftCandle[i] = lastCandle;
}
lastCandle = -1;
for (let i = s.length - 1; i >= 0 ; i--) {
if (s[i] === '|') lastCandle = i;
rightCandle[i] = lastCandle;
}
const ans = [];
for (let [start, end] of queries) {
const left = rightCandle[start];
const right = leftCandle[end];
if (left !== -1 && right !== -1 && left < right) {
ans.push(prefixSum[right] - prefixSum[left]);
} else {
ans.push(0);
}
}
return ans;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)