[数据结构与算法][leetcode] 2055蜡烛之间的盘子 | 前缀和

题目链接

在这里做出处理，让下标从1开始，询问的区间两端也+1
我们开两个数组：$nearL$以及$nearR$
$nearL[i]$表示：在$i$位置离着最近的左边的$|$符号是在哪一个下标
$nearR[i]$表示：在$i$位置离着最近的右边的$|$符号是在哪一个下标
如果说$s[i]={=}^{\prime }{|}^{\prime }$ 那么说$nearL[i]=i$并且$nearR[i]=i$
让左区间等于离着当前位置最近的右边的 |
让右区间等于离着当前位置最近的左边的 |
然后就可以直接开始前缀和了

Code:

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        const int N = s.size();
        int cnt2[N+7];
        vector<int> ans;
        s = "#" + s;
        int tot = queries.size();
        for(vector<int> &v:queries) {
            v[0] += 1;
            v[1] += 1;
        }
        int nearL[N+7], nearR[N+7];
        memset(nearL,0,sizeof nearL);
        memset(nearR,0,sizeof nearR);
        cnt2[0] = 0; 
        for (int i = 1;i <= N;i ++) {
            if(s[i] == '|') {
                cnt2[i] = cnt2[i-1];
                nearL[i] = i;
            } else {
                cnt2[i] = cnt2[i-1] + 1;
                nearL[i] = nearL[i-1];
            }
        }
        for(int i=N;i>=1;i--) {
            if(s[i] == '|') nearR[i] = i;
            else nearR[i] = nearR[i+1];
        }
        for(vector<int> v : queries) {
            int l = v[0], r = v[1];
            if(l == r) {
                ans.push_back(0);
                continue;
            }
            int tl,tr;
            tl = nearR[l];
            tr = nearL[r];
            if(tl >= tr) ans.push_back(0);
            else ans.push_back(cnt2[tr] - cnt2[tl-1]);
        }
        return ans;
    }
};