# 2055. Plates Between Candles
###### tags: `Leetcode` `Medium` `Greedy` `State Machine`
Link: https://leetcode.com/problems/plates-between-candles/description/
## 思路
对于给定的区间```[a,b]```里，需要算出```a```右边最近的蜡烛位置```x```，和```b```左边最近的蜡烛位置```y```。显然，我们可以用状态机的思想提前准备好```next```和```last```数组。```next[i]```表示```i```的下一个（可以是自身）出现蜡烛的位置；```last[i]```表示```i```的前一个（可以是自身）出现蜡烛的位置。这些都可以用o(n)实现。

知道了```x```和```y```，就可以用prefix sum求```[x,y]```内的盘子数量
## Code

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int[] preSum = new int[n];
        preSum[0]=(s.charAt(0)=='*'?1:0);
        for(int i=1; i<n; i++){
            preSum[i] = preSum[i-1]+(s.charAt(i)=='*'?1:0);
        }
        int[] next = new int[n];
        int[] prev = new int[n];
        next[n-1] = -1;
        prev[0] = -1;
        for(int i=n-1; i>=0; i--){
            if(s.charAt(i)=='|') next[i] = i;
            else if(i!=n-1) next[i] = next[i+1];
        }
        for(int i=0; i<n; i++){
            if(s.charAt(i)=='|') prev[i] = i;
            else if(i!=0) prev[i] = prev[i-1];
        }
        int[] ans = new int[queries.length];
        for(int i=0; i<queries.length; i++){
            int[] query = queries[i];
            int x = query[0], y = query[1];
            if(next[x]==-1 || prev[y]==-1) continue;
            x = next[x];
            y = prev[y];
            if(x<y) ans[i] = preSum[y]-(x==0?0:preSum[x-1]);
        }
        return ans;
    }
}