蜡烛之间的盘子

标签: 数组 字符串 二分查找 前缀和

难度: Medium

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] 表示 子字符串 s[lefti...righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。

  • 比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。

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

示例 1:

ex-1

输入：s = "**|**|***|", queries = [[2,5],[5,9]]
输出：[2,3]
解释：
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。

示例 2:

ex-2

输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
输出：[9,0,0,0,0]
解释：
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。

提示：

  • 3 <= s.length <= 105
  • s 只包含字符 '*' 和 '|' 。
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= lefti <= righti < s.length

Submission

运行时间: 164 ms

内存: 47.7 MB

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        preSum = [0] * n 
        sum_ = 0
        left = [0] * n 
        l = -1 
        for i, ch in enumerate(s):
            if ch == '*':
                sum_ += 1 
            else:
                l = i 
            preSum[i] = sum_ # 表示前i个位置有多少个盘子 '*｜**' -> [1,1,2,3]
            left[i] = l # 表示i这个位置的时候，右端点左侧的第一个蜡烛

        right = [0] * n
        r = -1 
        # 找区间左端点右侧最近的蜡烛
        for i in range(n - 1, -1, -1):
            if s[i] == '|':
                r = i 
            right[i] = r 
        
        ans = [0] * len(queries)
        for i, (x, y) in enumerate(queries):
            left_cand, right_cand = right[x], left[y]
            if left_cand >= 0 and right_cand >= 0 and left_cand < right_cand:
                ans[i] = preSum[right_cand] - preSum[left_cand]
        return ans

Explain

此题解采用了预处理数组的方法来优化查询。首先，使用前缀和数组 preSum 来记录从字符串开头到当前位置的盘子数量。其次，使用两个数组 left 和 right 分别存储每个位置左侧最近的蜡烛位置和右侧最近的蜡烛位置。通过这种方式，对于每一个查询，可以快速找到查询范围内左侧和右侧的第一个蜡烛，并计算这两个蜡烛之间的盘子数量。

时间复杂度: O(n + q)

空间复杂度: O(n)

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        preSum = [0] * n  # 前缀和数组，记录到每个位置为止的盘子数量
        sum_ = 0
        left = [0] * n  # 记录每个位置左侧最近的蜡烛位置
        l = -1
        for i, ch in enumerate(s):
            if ch == '*':
                sum_ += 1  # 遇到盘子，增加计数
            else:
                l = i  # 更新最近的蜡烛位置
            preSum[i] = sum_
            left[i] = l

        right = [0] * n  # 记录每个位置右侧最近的蜡烛位置
        r = -1
        for i in range(n - 1, -1, -1):
            if s[i] == '|':
                r = i  # 更新最近的蜡烛位置
            right[i] = r

        ans = [0] * len(queries)
        for i, (x, y) in enumerate(queries):
            left_cand, right_cand = right[x], left[y]  # 查询区间内的两个蜡烛位置
            if left_cand >= 0 and right_cand >= 0 and left_cand < right_cand:
                ans[i] = preSum[right_cand] - preSum[left_cand]  # 计算两蜡烛之间的盘子数量
        return ans

Explore

使用前缀和数组记录盘子的数量可以大大优化性能。如果直接在处理每个查询时统计盘子数量，我们需要对每个查询区间进行遍历，这在最坏情况下的时间复杂度是O(n*m)，其中n是字符串的长度，m是查询的数量。通过使用前缀和数组，我们可以预处理出一个数组，在O(1)的时间内回答任何区间内盘子的数量，从而使得每个查询的时间复杂度降低到O(1)，整体上查询的总时间复杂度为O(m)。

在这种情况下，left数组在起始位置很长一段将记录为-1，表示没有找到任何蜡烛；right数组在结束位置很长一段也将记录为-1。在处理查询时，我们检查由right和left数组确定的蜡烛位置。如果这些位置为-1，说明在查询区间内没有蜡烛，或者蜡烛不满足在所查询的子区间内的条件。这种方式确保了即使在没有蜡烛的长段中，算法仍能正确地返回结果0，因为没有蜡烛意味着没有盘子可以被计数。

从右向左遍历字符串s来构建right数组是为了记录每个位置右侧最近的蜡烛位置。这种从右向左的遍历方式允许我们在单次遍历中有效地更新右侧最近的蜡烛位置。如果我们只从左向右遍历，则无法在遍历过程中知道右侧的蜡烛位置，因此需要从右向左遍历以适应这一要求。

如果查询区间内没有蜡烛，则由right数组和left数组所确定的蜡烛位置将为-1。在算法实现中，我们首先检查由right[x]和left[y]确定的蜡烛位置是否有效（即不为-1）且right[x]小于left[y]。如果这些条件不满足，则查询区间内没有有效的蜡烛，因此返回的盘子数量应为0。这确保了在没有蜡烛的情况下算法返回正确的结果。