顺义青岛网站建设,提供wordpress主题和插件,做餐饮连锁在哪个网站看,广州安全教育平台官网【LetMeFly】2398.预算内的最多机器人数目#xff1a;滑动窗口单调队列——思路清晰的一篇题解
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-number-of-robots-within-budget/
你有 n 个机器人#xff0c;给你两个下标从 0 开始的整数数组 chargeTimes …【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 n1 n 5 * 1041 chargeTimes[i], runningCosts[i] 1051 budget 1015
解题方法滑动窗口单调队列
如果题目要求是k * sum(runningCosts) ≤ budget应该怎么做呢很简单一个滑动窗口即可。 使用两个指针l和r分别指向所选区间的左端点和右端点每次右指针r向右移动一位若窗口中所选元素的k * sum(runningCosts) budget则不断往后移动左指针直到k * sum(runningCosts) ≤ budget为止就得到了以r为右端点时最大的可选机器人数。 从l到r的元素是被选中的元素被称为“窗口”。这得益于窗口中元素数量越多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和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/142218259
