怎么做健康咨询网站,wordpress多级分类文章,梁山网站建设,公司网站域名是什么2398. 预算内的最多机器人数目
today 2398. 预算内的最多机器人数目
题目描述
你有 n 个机器人#xff0c;给你两个下标从0开始的整数数组 chargeTimes 和 runningCosts #xff0c;两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间#xff0c;花费 ru…2398. 预算内的最多机器人数目
today 2398. 预算内的最多机器人数目
题目描述
你有 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
选择前 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
题目解析
解题思路双指针单调队列。
我们首先可以使用双指针来维护一个窗口窗口的左右边界分别为 left 和 right。 表示在left 和right之间的机器人可以正常运行。 如果left 和right之间数值的和大于budget我们需要缩小窗口向右移动left直到窗口内的机器人数目小于等于budget。 同时我们使用一个单调队列来维护窗口内机器人的chargeTimes 最大值。 遍历过程中right-left1的最大值即为最多可以连续运行的机器人数目。
单调队列实现方法
维护一个单调递减的队列max_charge初始为空。对于每个新加入机器人对应的chargeTime即chargeTimes[right]如果chargeTime大于队尾元素则将队尾元素弹出直到队尾元素大于等于chargeTime,将chargeTime入队。这样保证了max_charge队列是单调递减的。max_charge队头元素即为当前窗口内的最大充电时间。
复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
代码实现
Python实现:
from collections import dequeclass Solution:def maximumRobots(self, chargeTimes, runningCosts, budget):n len(chargeTimes)left 0sum_running_cost 0max_charge deque() # 单调队列用于存储当前窗口内的最大充电时间res 0for right in range(n):# 更新窗口内的运行成本总和sum_running_cost runningCosts[right]# 维护单调队列保证队列中的元素是递减的以便快速获得窗口内最大充电时间while max_charge and chargeTimes[right] max_charge[-1]:max_charge.pop()max_charge.append(chargeTimes[right])# 计算当前窗口的总开销while max_charge and max_charge[0] (right - left 1) * sum_running_cost budget:# 如果超出预算移动 left 缩小窗口并更新相关值if chargeTimes[left] max_charge[0]:max_charge.popleft()sum_running_cost - runningCosts[left]left 1# 更新最大运行机器人数res max(res, right - left 1)return resGo实现:
func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {n:len(chargeTimes)left,right:0,0sum_cost,ans:0,0max_charge:make([]int,0)for right0;rightn;right{//更新窗口内的运行成本总和sum_costrunningCosts[right]//维护单调队列保证队列中的元素是递减的以便快速获得窗口内最大充电时间for len(max_charge)0 max_charge[len(max_charge)-1]chargeTimes[right]{max_chargemax_charge[:len(max_charge)-1]}max_chargeappend(max_charge,chargeTimes[right])for leftright max_charge[0](right-left1)*sum_costint(budget){//如果超出预算移动 left 缩小窗口并更新相关值if chargeTimes[left]max_charge[0]{max_chargemax_charge[1:]}sum_cost-runningCosts[left]left}ansmax(ans,right-left1)}return ans}C实现:
class Solution {
public:int maximumRobots(vectorint chargeTimes, vectorint runningCosts, long long budget) {int n chargeTimes.size();int left 0;long long sum_cost 0;int ans 0;dequeint max_charge;for (int right 0; right n; right) {// 更新窗口内的运行成本总和sum_cost runningCosts[right];// 维护单调队列保证队列中的元素是递减的以便快速获得窗口内最大充电时间while (!max_charge.empty() max_charge.back() chargeTimes[right]) {max_charge.pop_back();}max_charge.push_back(chargeTimes[right]);// 如果超出预算移动 left 缩小窗口并更新相关值while (left right max_charge.front() (right - left 1) * sum_cost budget) {if (chargeTimes[left] max_charge.front()) {max_charge.pop_front(); // 移除最大充电时间}sum_cost - runningCosts[left];left;}// 更新最大可运行的机器人数量ans max(ans, right - left 1);}return ans;}
};
