leetcode 2398.预算内的最多机器人数目

2398.预算内的最多机器人数目

题意：

解析：

需要注意的是，题目询问中连续是子数组的意思，即求满足条件的最长子数组的长度。

因为是连续的，所以可以用双指针扫描整个数组。每次将右指针 $r$ 向右移动一个位置，然后左指针 $l$ 向右移动到满足 budget 限制的位置。

判断区间 [l,r] 是否满足budget 限制。在扫描时，可以用一个变量维护区间 cost 的和，也可以通过前缀和来得到 sum(cost)。除此之外，需要这段区间 times 的最大值，维护一个非严格递减的单调队列，队首元素是这段区间 times 的最大值。

在将左指针 $l$ 右移的时候，需要判断单调队列队首元素是否已经失效。

代码：

int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {int n = chargeTimes.size();deque<int> q;long long sum = 0;int ans = 0;for(int l = 0, r = 0; r < n; r++){sum += runningCosts[r];while(q.size() && chargeTimes[q.back()] < chargeTimes[r])q.pop_back();q.push_back(r);while(q.size() && chargeTimes[q.front()] + (r-l+1) * sum > budget){sum -= runningCosts[l++];if(q.front() < l)q.pop_front();                 }ans = max(ans, r-l+1);}return ans;}