力扣2398.预算内的最多机器人数目
力扣2398.预算内的最多机器人数目
-
双指针
- 遍历右指针
- 同时记录l - r区间的sum以及最大值
- 如果超出预算就移动左指针
-
class Solution { public: int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) { int res=0; deque<int> q; long sum = 0L; for(int l=0,r=0;r<chargeTimes.size();r++) { while(!q.empty() && chargeTimes[r] >= chargeTimes[q.back()]) q.pop_back(); q.push_back(r); sum += runningCosts[r]; while(!q.empty() && chargeTimes[q.front()] + (r - l + 1)*sum > budget) { if(q.front() == l) q.pop_front(); sum -= runningCosts[l++]; } res = max(res,r - l + 1); } return res; } };
原文地址:https://blog.csdn.net/Pisasama/article/details/140520716
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!