当前位置: 首页 > news >正文

宾爵手表官方网站太原互联网推广公司

宾爵手表官方网站,太原互联网推广公司,光辉网站建设,建材网站制作2398. 预算内的最多机器人数目 today 2398. 预算内的最多机器人数目 题目描述 你有 n 个机器人,给你两个下标从0开始的整数数组 chargeTimes 和 runningCosts ,两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间,花费 ru…

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

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

题目描述

你有 n 个机器人,给你两个下标从0开始的整数数组 chargeTimesrunningCosts ,两者长度都为 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 == n
  • 1 <= n <= 5*10^4
  • 1 <= chargeTimes[i], runningCosts[i] <= 10^5
  • 1 <= budget <= 10^15

题目解析

解题思路:双指针+单调队列。

我们首先可以使用双指针来维护一个窗口,窗口的左右边界分别为 leftright。 表示在leftright之间的机器人,可以正常运行。
如果leftright之间数值的和大于budget,我们需要缩小窗口,向右移动left,直到窗口内的机器人数目小于等于budget
同时,我们使用一个单调队列来维护窗口内机器人的chargeTimes 最大值。
遍历过程中right-left+1的最大值,即为最多可以连续运行的机器人数目。

单调队列实现方法:

  1. 维护一个单调递减的队列max_charge,初始为空。
  2. 对于每个新加入机器人对应的chargeTimechargeTimes[right],如果chargeTime大于队尾元素,则将队尾元素弹出直到队尾元素大于等于chargeTime,将chargeTime入队。这样保证了max_charge队列是单调递减的。
  3. 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 res

Go实现:

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 right=0;right<n;right++{//更新窗口内的运行成本总和sum_cost+=runningCosts[right]//维护单调队列,保证队列中的元素是递减的,以便快速获得窗口内最大充电时间for len(max_charge)>0 && max_charge[len(max_charge)-1]<chargeTimes[right]{max_charge=max_charge[:len(max_charge)-1]}max_charge=append(max_charge,chargeTimes[right])for left<=right && max_charge[0]+(right-left+1)*sum_cost>int(budget){//如果超出预算,移动 left 缩小窗口,并更新相关值if chargeTimes[left]==max_charge[0]{max_charge=max_charge[1:]}sum_cost-=runningCosts[left]left++}ans=max(ans,right-left+1)}return ans}

C++实现:

class Solution {
public:int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {int n = chargeTimes.size();int left = 0;long long sum_cost = 0;int ans = 0;deque<int> 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;}
};
http://www.hrbkazy.com/news/53415.html

相关文章:

  • 驻马店做网站公司如何做好口碑营销
  • 网站设计素材优化大师电视版
  • wordpress_主题教程济南seo公司
  • 算命公司网站建设制作开发方案seo标题优化的心得总结
  • 江苏省镇江市丹阳市疫情最新消息郑州seo优化外包热狗网
  • 7月新闻大事件30条全专业优化公司
  • 上海网站建设 迈seo文章是什么意思
  • 长沙网站seo收费标准3分钟搞定网站seo优化外链建设
  • 关于内网站建设的请示培训机构哪家好
  • 顺义网站建设廊坊seo排名公司
  • 怎么做网站的后台管理系统手机百度高级搜索
  • 望野什么意思郑州网络seo公司
  • 建设优化一个网站步骤最佳搜索引擎
  • wordpress中文转拼音长春网站优化咨询
  • 企业网站优化的三层含义属于seo网站优化
  • wordpress插件随机文章西安seo报价
  • 中国建设网官方网站发改委移动排名提升软件
  • 网络营销型网站设计竞价托管一般多少钱
  • 网站重要性全部列表支持安卓浏览器软件下载
  • 网上哪里有辅导高考生做难题的网站短链接生成网址
  • 新开传奇网站排行一键识图找原图
  • 怎么做自动跳转网站怎么优化一个网站
  • 做系统后怎么找回网站收藏夹广告联盟下载app
  • 常州网站建设公司如何网络运营需要学什么
  • 网站开发行业竞争大吗网络营销方案设计
  • wordpress 悬浮联系百度seo收录软件
  • wordpress 关闭插件更新优化网站标题和描述的方法
  • 龙华营销型网站建设公司软件开发需要学什么
  • 江苏做网站公司拉人头最暴利的app
  • wordpress子域名网站磁力链最佳的搜索引擎