一、题目
你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。
请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。
示例 1：
输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25 输出：3 解释： 可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。 选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。 可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。
示例 2：
输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19 输出：0 解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。
提示：
chargeTimes.length == runningCosts.length == n1 <= n <= 5 * 10^41 <= chargeTimes[i], runningCosts[i] <= 10^51 <= budget <= 10^15
二、解题思路
我们需要找到在不超过 budget 的前提下，可以连续运行的机器人的最大数量。总开销的计算公式为：
其中，k是连续运行的机器人数目。
核心思路
-
滑动窗口：
-
使用双指针维护一个滑动窗口，表示当前连续运行的机器人区间。
-
窗口的左边界为
left，右边界为right。
-
-
单调队列：
-
使用单调队列维护当前窗口中的最大值（
chargeTimes的最大值）。 -
单调队列的性质是队首始终是当前窗口的最大值。
-
-
窗口扩展与收缩：
-
扩展窗口：右指针
right向右移动，将新的机器人加入窗口。 -
收缩窗口：如果当前窗口的总开销超过
budget，则左指针left向右移动，缩小窗口。
-
-
计算总开销：
-
使用前缀和数组快速计算
runningCosts的区间和。 -
使用单调队列快速获取当前窗口的
chargeTimes最大值。
-
三、代码实现
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>using namespace std;int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {int n = chargeTimes.size();int left = 0; // 滑动窗口的左边界long long sumRunningCosts = 0; // 当前窗口的 runningCosts 之和int maxRobots = 0; // 记录最大连续运行的机器人数目// 单调队列，存储 chargeTimes 的下标，队首是当前窗口的最大值deque<int> dq;// 遍历右边界for (int right = 0; right < n; ++right) {// 更新 runningCosts 的和sumRunningCosts += runningCosts[right];// 维护单调队列，确保队首是当前窗口的最大值while (!dq.empty() && chargeTimes[dq.back()] <= chargeTimes[right]) {dq.pop_back();}dq.push_back(right);// 计算当前窗口的总开销long long currentCost = chargeTimes[dq.front()] + (right - left + 1) * sumRunningCosts;// 如果总开销超过 budget，则收缩窗口while (currentCost > budget && left <= right) {sumRunningCosts -= runningCosts[left];if (dq.front() == left) {dq.pop_front(); // 如果队首是左边界，则移除}left++;if (left <= right) {currentCost = chargeTimes[dq.front()] + (right - left + 1) * sumRunningCosts;}}// 更新最大连续运行的机器人数目if (currentCost <= budget) {maxRobots = max(maxRobots, right - left + 1);}}return maxRobots;
}int main() {// 示例 1vector<int> chargeTimes1 = {3, 6, 1, 3, 4};vector<int> runningCosts1 = {2, 1, 3, 4, 5};long long budget1 = 25;cout << "结果: " << maximumRobots(chargeTimes1, runningCosts1, budget1) << endl;return 0;
}通过滑动窗口和单调队列的结合，我们可以高效地解决这个问题。滑动窗口用于维护连续运行的机器人区间，单调队列用于快速获取区间内的最大值，从而动态计算总开销并调整窗口大小。
时间复杂度：O(n)O(n)，每个元素最多被加入和弹出单调队列一次。
空间复杂度：O(n)O(n)，用于存储单调队列。
