1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// @Title: 蜡烛之间的盘子 (Plates Between Candles)
// @Author: 15816537946@163.com
// @Date: 2022-03-08 23:51:58
// @Runtime: 244 ms
// @Memory: 19.4 MB
func platesBetweenCandles(s string, queries [][]int) []int {
    n := len(s)
    preSum := make([]int, n)
    left := make([]int, n)
    sum, l := 0, -1
    for i, ch := range s {
        if ch == '*' {
            sum++
        } else {
            l = i
        }
        preSum[i] = sum
        left[i] = l
    }

    right := make([]int, n)
    for i, r := n-1, -1; i >= 0; i-- {
        if s[i] == '|' {
            r = i
        }
        right[i] = r
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        x, y := right[q[0]], left[q[1]]
        if x >= 0 && y >= 0 && x < y {
            ans[i] = preSum[y] - preSum[x]
        }
    }
    return ans
}