DeepSeek LeetCode 2398. 预算内的最多机器人数目 public int maximumRobots(int[] chargeTimes, int[]

这道题是典型的滑动窗口 + 单调队列问题。
核心条件是：

· 选定连续的子数组（机器人下标连续）
· 总费用 = max(chargeTimes[i..j]) + (j-i+1) * sum(runningCosts[i..j])
· 要求总费用 ≤ budget
· 返回最长的子数组长度

思路

1. 用滑动窗口维护区间 [left, right]
2. 用单调递减队列快速获取当前窗口内的 maxChargeTimes
3. 若当前窗口费用超预算，收缩左边界
4. 每次记录窗口最大长度

---

代码

```java
class Solution {
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
int n = chargeTimes.length;
Deque<Integer> deque = new ArrayDeque<>(); // 存储索引，队首为最大 chargeTimes 的索引
long sumRunning = 0;
int left = 0;
int ans = 0;

for (int right = 0; right < n; right++) {
// 1. 维护单调递减队列
while (!deque.isEmpty() && chargeTimes[deque.peekLast()] <= chargeTimes[right]) {
deque.pollLast();
}
deque.offerLast(right);

// 2. 累加 runningCosts
sumRunning += runningCosts[right];

// 3. 若费用超预算，移动左边界
while (!deque.isEmpty() &&
chargeTimes[deque.peekFirst()] + (right - left + 1) * sumRunning > budget) {
// 如果左边界正好是队首元素，则弹出
if (deque.peekFirst() == left) {
deque.pollFirst();
}
sumRunning -= runningCosts[left];
left++;
}

// 4. 更新答案
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
```

---

复杂度

· 时间：O(n)，每个元素最多入队出队一次
· 空间：O(n)，单调队列空间

---

示例

输入：

```
chargeTimes = [3,6,1,3,4]
runningCosts = [2,1,3,4,5]
budget = 25
```

输出：

```
3
```