力扣2055.蜡烛之间的盘子
力扣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; } };
原文地址:https://blog.csdn.net/Pisasama/article/details/140080393
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!