参考了官方的答案后理解在自己写的。
- 使用双指针模式。i为右区间指针，k为左区间指针。i递增，k根据条件，结果要是超过了budget后也递增1。取每次符合条件的
[k,i]之间的数量最大值返回。 - 使用队列维护
chargeTimes[k-i]的最大值的下标。
这里我看了参考答案后想着直接将
chargeTimes[k-i]的值全部保存到队列中，计算的时候再用max去取最大值就行。理论上是可行的，但是提交的时候报超时了。AC不了
from collections import deque
from typing import List
class Solution:
def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
k = 0
dq = deque()
running_costs_sum = 0
res = 0
for i in range(len(chargeTimes)):
running_costs_sum += runningCosts[i]
while dq and chargeTimes[dq[-1]] <= chargeTimes[i]:
dq.pop()
dq.append(i)
while k <= i and (i - k + 1) * running_costs_sum + chargeTimes[dq[0]] > budget:
if dq and dq[0] == k:
dq.popleft()
running_costs_sum -= runningCosts[k]
k += 1
res = max(res, i - k + 1)
return res