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

LeetCode 2398.预算内的最多机器人数目:滑动窗口+单调队列——思路清晰的一篇题解

【LetMeFly】2398.预算内的最多机器人数目:滑动窗口+单调队列——思路清晰的一篇题解

力扣题目链接:https://leetcode.cn/problems/maximum-number-of-robots-within-budget/

你有 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 == n
  • 1 <= n <= 5 * 104
  • 1 <= chargeTimes[i], runningCosts[i] <= 105
  • 1 <= budget <= 1015

解题方法:滑动窗口+单调队列

如果题目要求是k * sum(runningCosts) ≤ budget应该怎么做呢?很简单,一个滑动窗口即可。

使用两个指针lr分别指向所选区间的左端点和右端点,每次右指针r向右移动一位,若窗口中所选元素的k * sum(runningCosts) > budget,则不断往后移动左指针,直到k * sum(runningCosts) ≤ budget为止,就得到了以r为右端点时,最大的可选机器人数。

lr的元素是被选中的元素,被称为“窗口”。这得益于窗口中元素数量越多,k * sum(runningCosts)就越大。

由于左指针和右指针都至多遍历一次数组,所以总时间复杂度为 O ( n ) O(n) O(n)

但是这道题的总开销是max(chargeTimes) + k * sum(runningCosts),而不是k * sum(runningCosts)k = r - l + 1,而sum(runningCosts)只需要在移动左右指针的时候使用一个变量来维护即可在 O ( 1 ) O(1) O(1)的时间内得到。对于一个窗口,max(chargeTimes)如何在 O ( 1 ) O(1) O(1)的时间内得到呢?这就需要引入单调队列。

使用一个单调递减队列,保持越靠近队首的元素严格靠近越靠近队尾的元素。

具体来说,当r加入窗口时,若chargeTimes[r] > 队尾元素,则队尾元素不断出栈。之后再将r入栈。这样,栈中的元素就保持了单调递减。而当l退出窗口时,如果队首元素就是l,则l出队。

这样做有一个好处,由于队列是单调递减的,所以队首元素就是窗口中chargeTimes最大的那个元素。诶,max(chargeTimes)也能在 O ( 1 ) O(1) O(1)时间复杂度内得到了,问题解决。

注意,队列的作用只是为了计算窗口中的max(chargeTimes)。若队列中一个元素被chargeTimes更大的r“顶”出队列,则并不代表其不在窗口中了,而只是说明其chargeTimes值比较小。

  • 时间复杂度 O ( l e n ( c h a r g e T i m e s ) ) O(len(chargeTimes)) O(len(chargeTimes))
  • 空间复杂度 O ( l e n ( c h a r g e T i m e s ) ) O(len(chargeTimes)) O(len(chargeTimes))

AC代码

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/142218259


http://www.kler.cn/news/303197.html

相关文章:

  • 工业设备网关在智能工厂建设中发挥的作用,以某汽车制造厂为例
  • LabVIEW编程语言出于什么原因开发的?
  • 1688商品详情API返回值中的售后保障与服务信息
  • Failed building wheel for opencv-python-headless
  • k8s常用指令续:
  • Day 11-12:查找
  • day14-单例设计模式动态代理
  • Qt 学习第八天:菜单栏、工具栏、状态栏、模态和非模态对话框创建
  • RabbitMQ延迟消息——DelayExchange插件
  • Python之 条件与循环(Python‘s Conditions and loops)
  • 在麒麟系统 v10 SP3 上运行自带的 MariaDB
  • 【鸿蒙】HarmonyOS NEXT星河入门到实战6-组件化开发-样式结构重用常见组件
  • Oracle中VARCHAR和VARCHAR2的区别
  • CSS框架 Tailwind CSS
  • Leetcode3276. 选择矩阵中单元格的最大得分
  • CNN中的conv
  • ASP.net core 8.0网站发布
  • 房产销售系统|基于java和vue的房产销售系统(源码+数据库+文档)
  • 利用apache-pdfbox库修改pdf文件模板,进行信息替换
  • 【基础算法总结】二分查找
  • 在Python的Pandas库中,`df.iloc[::500]`是一个用于数据选择的索引器,它允许我们从DataFrame中选择特定的行和列。
  • golang学习笔记19——golang做服务发现与注册的深度剖析
  • 从安装ffmpeg开始,把一个视频按照每秒30帧fps剪切为图片
  • Vue组件:模板引用ref属性的使用
  • 微信小程序之轮播图组件封装
  • CTF常见编码及加解密(超全)第二篇
  • java程序员入行科目一之CRUD轻松入门教程(二)
  • layui监听table表单的多选框
  • 高级实时通信:基于 Python 的 WebSocket 实现与异步推送解决方案
  • 商务办公tips1:如何将网页转换为pdf