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] 在蜡烛之间有九个盘子。
- 其他查询在蜡烛之间都没有盘子。

提示：

  • 3 <= s.length <= 10^5
  • s 只包含字符 ‘*’ 和 ‘|’。
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= lefti <= righti < s.length

解题思路

解题思路分析：

这道题的核心是找到每个查询区间内最左边和最右边的蜡烛，然后计算它们之间的盘子数量。

主要思路：

  1. 预处理蜡烛位置：由于查询很多，我们需要快速找到区间内的第一个和最后一个蜡烛。可以预先记录所有蜡烛的位置，然后使用二分查找快速定位。

  2. 前缀和优化计算：为了快速计算两个蜡烛之间的盘子数量，我们可以使用前缀和数组。前缀和数组记录从开头到当前位置的盘子总数。

  3. 处理查询：

    • 对于每个查询[left, right]，使用二分查找找到区间内第一个蜡烛位置firstCandle和最后一个蜡烛位置lastCandle
    • 如果找不到两个蜡烛或firstCandle >= lastCandle，则该区间内没有被蜡烛包围的盘子
    • 否则，使用前缀和快速计算firstCandle和lastCandle之间的盘子数量

算法步骤：

  1. 遍历字符串s，记录所有蜡烛的位置到candlePos数组
  2. 构建前缀和数组prefixSum，prefixSum[i]表示s[0…i]中盘子的总数
  3. 对于每个查询，使用二分查找在candlePos中找到边界蜡烛
  4. 利用前缀和计算结果

这种方法的优势是预处理后每个查询都能在O(log n)时间内完成，整体效率很高。

代码实现

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> candlePos;
        vector<int> prefixSum(n + 1, 0);
        
        // 记录蜡烛位置和构建前缀和
        for (int i = 0; i < n; i++) {
            if (s[i] == '|') {
                candlePos.push_back(i);
            }
            prefixSum[i + 1] = prefixSum[i] + (s[i] == '*' ? 1 : 0);
        }
        
        vector<int> result;
        for (auto& query : queries) {
            int left = query[0], right = query[1];
            
            // 找到区间内第一个蜡烛位置
            auto it1 = lower_bound(candlePos.begin(), candlePos.end(), left);
            // 找到区间内最后一个蜡烛位置
            auto it2 = upper_bound(candlePos.begin(), candlePos.end(), right);
            
            if (it1 == candlePos.end() || it2 == candlePos.begin() || it1 >= it2 - 1) {
                result.push_back(0);
            } else {
                int firstCandle = *it1;
                int lastCandle = *(it2 - 1);
                result.push_back(prefixSum[lastCandle] - prefixSum[firstCandle + 1]);
            }
        }
        
        return result;
    }
};

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        import bisect
        
        n = len(s)
        candle_pos = []
        prefix_sum = [0] * (n + 1)
        
        # 记录蜡烛位置和构建前缀和
        for i in range(n):
            if s[i] == '|':
                candle_pos.append(i)
            prefix_sum[i + 1] = prefix_sum[i] + (1 if s[i] == '*' else 0)
        
        result = []
        for left, right in queries:
            # 找到区间内第一个蜡烛位置
            first_idx = bisect.bisect_left(candle_pos, left)
            # 找到区间内最后一个蜡烛位置
            last_idx = bisect.bisect_right(candle_pos, right) - 1
            
            if first_idx >= len(candle_pos) or last_idx < 0 or first_idx >= last_idx:
                result.append(0)
            else:
                first_candle = candle_pos[first_idx]
                last_candle = candle_pos[last_idx]
                result.append(prefix_sum[last_candle] - prefix_sum[first_candle + 1])
        
        return result

public class Solution {
    public int[] PlatesBetweenCandles(string s, int[][] queries) {
        int n = s.Length;
        List<int> candlePos = new List<int>();
        int[] prefixSum = new int[n + 1];
        
        // 记录蜡烛位置和构建前缀和
        for (int i = 0; i < n; i++) {
            if (s[i] == '|') {
                candlePos.Add(i);
            }
            prefixSum[i + 1] = prefixSum[i] + (s[i] == '*' ? 1 : 0);
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int left = queries[i][0], right = queries[i][1];
            
            // 找到区间内第一个蜡烛位置
            int firstIdx = BinarySearchLeft(candlePos, left);
            // 找到区间内最后一个蜡烛位置
            int lastIdx = BinarySearchRight(candlePos, right) - 1;
            
            if (firstIdx >= candlePos.Count || lastIdx < 0 || firstIdx >= lastIdx) {
                result[i] = 0;
            } else {
                int firstCandle = candlePos[firstIdx];
                int lastCandle = candlePos[lastIdx];
                result[i] = prefixSum[lastCandle] - prefixSum[firstCandle + 1];
            }
        }
        
        return result;
    }
    
    private int BinarySearchLeft(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int BinarySearchRight(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[]}
 */
var platesBetweenCandles = function(s, queries) {
    const n = s.length;
    const candlePos = [];
    const prefixSum = new Array(n + 1).fill(0);
    
    // 记录蜡烛位置和构建前缀和
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + q log c)n为字符串长度，q为查询数量，c为蜡烛数量。预处理O(n)，每个查询二分查找O(log c)
空间复杂度O(n + c)前缀和数组O(n)，蜡烛位置数组O(c)

相关题目