2398.maximumRobots

. - 力扣（LeetCode）

参考了官方的答案后理解在自己写的。

• 使用双指针模式。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