2055. 蜡烛之间的盘子（Rating 1819）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

2055. 蜡烛之间的盘子

Rating 1819

思路

对于每一个query，我们需要找到

1. 左端点右边最靠近它的蜡烛
2. 右端点左边最靠近它的蜡烛

显然这两个值都可以通过维护“前缀和”来快速求出。

如从左向右遍历时，对于每个位置维护遍历过程中最新的蜡烛的位置，即是“右端点左边最靠近它的蜡烛”。反之同理。

得到两端蜡烛的位置后，通过前缀和来求出中间的盘子数量。

代码

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        presum = [0] * (n + 1) # 盘子对应前缀和
        idx_left_list = [-1] * (n + 1) # 右端点左边最靠近它的蜡烛，初始化为-1
        idx_right_list = [-1] * (n + 1) # 左端点右边最靠近它的蜡烛，初始化为-1
        for idx, c in enumerate(s):
            presum[idx + 1] = presum[idx] + (c == '*') # 盘子对应前缀和
            idx_left_list[idx + 1] = idx if c == '|' else idx_left_list[idx] # 右端点左边最靠近它的蜡烛
            jdx = n - 1 - idx # 从右向左遍历
            d = s[jdx]
            idx_right_list[jdx] = jdx if d == '|' else idx_right_list[jdx + 1] # 左端点右边最靠近它的蜡烛
            
        ret = [0] * len(queries)
        for idx, (l, r) in enumerate(queries):
            left = idx_right_list[l]
            right = idx_left_list[r + 1]
            if left == -1 or right == -1 or left >= right: # 没有蜡烛
                ret[idx] = 0
            else:
                ret[idx] = presum[right] - presum[left]
        return ret