参考了官方的答案后理解在自己写的。
- 使用双指针模式。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