2398.预算内的最多机器人数目 滑动窗口+单调队列

        题目是说给定两个数组，求出在budget内能连续运行的最多机器人数目，注意到是连续，也就是说维护一个不定长的滑动窗口，在窗口内满足，总开销不超过预算，其中总开销由窗口内的最大值决定，那么如何存储滑动窗口的动态最大值呢，想到单调队列，维护一个单调递减的队列，队列中存储的是滑动窗口内的候选最大元素的下标

        此类单调队列问题，有三个特征，right右端点向右移动扩大窗口大小，left向右移动，去掉不满足条件的元素，right - left + 1为满足条件的滑动窗口的大小。

        单调队列模板请看239. 滑动窗口最大值-CSDN博客

        代码

class Solution {
public:int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {int n = chargeTimes.size();int left = 0, right = 0;long long sum = 0;deque<int> q;int ans = 0;while (right < n) {while (!q.empty() && chargeTimes[q.back()] <= chargeTimes[right]) {q.pop_back();}q.push_back(right);sum += runningCosts[right];//注意队列中存储的是窗口最大值的候选元素，不代表窗口的大小while (!q.empty() && chargeTimes[q.front()] + (right - left + 1) * sum > budget) {if (q.front() == left) q.pop_front();sum -= runningCosts[left];left++;}ans = max(ans,right - left + 1);right++;}return ans;}
};