https://leetcode.cn/problems/maximum-number-of-robots-within-budget/solution/by-qingfengpython-y8g8/
难度：困难
你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。 第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。 运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ， 其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。 请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。
提示：
- chargeTimes.length == runningCosts.length == n
- 1 <= n <= 5 * 10 ^ 4
- 1 <= chargeTimes[i], runningCosts[i] <= 10 ^ 5
- 1 <= budget <= 10 ^ 15
示例 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 。
遇到这种场景分析类的题目，需要认真多读几遍题干。题目为了帮助大家理解已经加粗表示了最多、连续这几个关键字。
遇到在不超过某场景的情况下对连续的数组，求最多(长)的问题，一般都可以使用滑动窗口来进行解题。
对于滑动窗口只需要关注一个问题： 什么时候收缩左边界？
对于这道题来说，题目给出了我们总开销公式：
max(chargeTimes) + k * sum(runningCosts)
当数组的总开销超过了budget，则需要收缩左边界。
注意：
很多书上说的收缩左边界都是while 循环直到满足条件，再停止收缩。
但对于求最长的场景，无需这么做。遇到不满足的时候，保持最大窗口-1，即left += 1即可。
因为如果不能满足-1后的下一次满足条件，那就没办法超过当前最大值，没必要持续的缩减了。
比赛的时候看了下用例范围只有10 ^ 5，就盲目的直接求max了，结果吃了AW超时。
在写代码之前，先来讨论下滑动窗口遍历的过程中，范围内求最值的方法：
- 最简单的方式莫过于，针对滑窗的左右边界，求max(arrays[left,right])，其时间复杂度为O(N)。
- 使用字典将相同的数字合并起来计数，然后设置最值变量。
# 伪代码
from collections import defaultdict
arrays = [3,6,1,3,4]
max_num = float('-inf')
d = defaultdict(int)
left = 0
for r,val in enumerate(arrays):
# 比较当前遍历的数组数值与最大值
max_num = max(max_num, val)
# 将当前val加入字典
d[val] += 1
# 判断是否需要收缩左边界，如果需要执行下列判断
if True: # 需要收缩左边界
# 最边界的数唯一，则需要删除掉
if d[arrays[left]] == 1:
if max_num == d.pop(arrays[left]):
# 重新从字典的key中获取最大值
max_num = max(d)
else:
d[arrays[left]] -= 1上面的代码复杂度比较高，但对于初学者来说，更易于理解。时间复杂度上需要根据用例来评估，最好O(1)，最差O(N)。 3. 单调队列求最值 使用单调队列的方式求最值，最符合滑窗求最值的方式，但丹玉新手，可能在理解上存在一定难度。 单调队列的使用方式：
- 队列中存储的不是数组的值，而是数组下标
- 当增大窗口(右边界伸展)时，判断队尾值与当前右边界值的单调性。不满足单调性则队尾持续出队，最终将右边界下标入队。
- 当最小串口(左边界收缩)时，队首出队即可。
# 伪代码
from collections import deque
arrays = [3,6,1,3,4]
dq = deque()
left = 0
for r,val in enumerate(arrays):
while dq and arrays[dq[-1]] <= val:
dq.pop()
dq.append(r)
# 判断是否需要收缩左边界，如果需要执行下列判断
while dq and True: # 需要收缩左边界
dq.popleft()Python:
from collections import deque
class Solution:
def maximumRobots(self, chargeTimes, runningCosts, budget):
dq = deque()
left = total = ret = 0
for i, val in enumerate(chargeTimes):
while dq and chargeTimes[dq[-1]] <= val:
dq.pop()
dq.append(i)
total += runningCosts[i]
if dq and chargeTimes[dq[0]] + (i - left + 1) * total > budget:
total -= runningCosts[left]
if dq[0] == left:
dq.popleft()
left += 1
ret = max(ret, i - left + 1)
return retJava:
class Solution {
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
Deque<Integer> dq = new LinkedList<>();
int left = 0, ret = 0;
long total = 0;
for (int i = 0; i < chargeTimes.length; i++) {
while (!dq.isEmpty() && chargeTimes[dq.peekLast()] <= chargeTimes[i]) {
dq.pollLast();
}
dq.add(i);
total += runningCosts[i];
if (!dq.isEmpty() && chargeTimes[dq.peek()] + (long) (i - left + 1) * total > budget) {
total -= runningCosts[left];
if (dq.peek() == left) {
dq.pollFirst();
}
left++;
}
ret = Math.max(ret, i - left + 1);
}
return ret;
}
}欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！
我的个人博客：https://qingfengpython.cn