比格设计网站官网_网页界面设计的特点_pageadmin建站系统_百度指数怎么刷指数方法

一、题目

1、题目描述

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。

运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。

请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。

2、接口描述

python3

 ​

class Solution:def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:

cpp

class Solution {
public:int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {}
};

3、原题链接

2398. Maximum Number of Robots Within Budget

---

二、解题报告

1、思路分析

固定右端点r，r右移其合法左端点l不会后退，具有单调性，考虑滑窗

由于要获取滑窗最值，考虑单调队列

维护一个单调队列，队头到队尾chargeTime单调递减，即队头最大

i 代表窗口右端点，j 代表窗口左端点

那么过程中当 花费 > budget，往右收缩 j 同时根据 j 来弹出队头

维护i - j + 1的最大值即可

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

python3

 ​

class Solution:def maximumRobots(self, chargeTimes: list[int], runningCosts: list[int], budget: int) -> int:n = len(chargeTimes)tc = list(zip(chargeTimes, runningCosts))dq = deque()s = 0res = 0j = 0for i, (t, c) in enumerate(tc):s += cwhile dq and t >= tc[dq[-1]][0]:dq.pop()dq.append(i)while dq and tc[dq[0]][0] + (i - j + 1) * s > budget:if dq[0] == j: dq.popleft()s -= tc[j][1]j += 1res = max(res, i - j + 1)        return res

cpp

 ​

class Solution {
public:int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {std::deque<int> dq;int res = 0;long long s = 0;int n = chargeTimes.size();for (int i = 0, j = 0; i < n; ++ i) {s += runningCosts[i];while (dq.size() && chargeTimes[i] >= chargeTimes[dq.back()]) dq.pop_back();dq.push_back(i);while (dq.size() && chargeTimes[dq.front()] + (i - j + 1) * s > budget) {if (dq.front() == j) dq.pop_front();s -= runningCosts[j ++];}res = std::max(res, i - j + 1);}return res;}
};

 ​