台州网站推广百度云资源搜索引擎

【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应该怎么做呢？很简单，一个滑动窗口即可。

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

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

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

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

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

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

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

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

• 时间复杂度$O(len(chargeTimes))$
• 空间复杂度$O(len(chargeTimes))$

AC代码

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

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