力扣2055.蠟燭之間的盤子

• 預處理每個元素左右最近的蠟燭下標

  • 同時求前綴和
  • 遍歷每個詢問
  • 找到左右端點對應的內部的最近蠟燭(最大區間)

•   class Solution {public:vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {vector<int> l(s.length(), 0), r(s.length(), 0);vector<int> sum(s.length() + 1, 0);int p = -1,q = -1;for(int i=0,j=s.size()-1;i<s.size();i++,j--){//pq為最近的蠟燭下標if(s[i] == '|') p = i;if(s[j] == '|') q = j;l[i] = p,r[j] = q;sum[i+1] = sum[i] + (s[i] == '*' ? 1 : 0);}vector<int> res(queries.size(),0);for(int i=0;i<queries.size();i++){int a = queries[i][0] , b = queries[i][1];//最大區間的左右端點int c = r[a],d = l[b];if(c != -1 && c <= d) res[i] = sum[d + 1] - sum[c];}return res;}};