What is the main strategy to solve Maximum Number of Robots Within Budget?

The key strategy is binary search over possible consecutive robot counts combined with a sliding window and monotonic queue to track sums and maximum charges.

Can this problem be solved without binary search?

A brute-force approach is possible but inefficient; binary search over possible lengths drastically reduces time complexity.

Why do we use a monotonic queue in this problem?

The monotonic queue allows O(1) retrieval of the maximum charge time in the current window, which is crucial for calculating total cost efficiently.

What should I watch out for in edge cases?

Be careful when no consecutive robots fit the budget; the solution should correctly return 0 in such cases.

How does GhostInterview optimize solving this pattern?

It converts the problem into a checkable binary search over window lengths and highlights efficient data structures to maintain max and sums, preventing common TLE errors.

#2398

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

预算内的最多机器人数目

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。运行 k 个机…

数组二分查找队列滑动窗口堆（优先队列）

题目描述

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。

运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。

请你返回在 不超过 budget 的前提下，你最多可以运行的连续的机器人数目为多少。

示例 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 。

提示：

chargeTimes.length == runningCosts.length == n
1 <= n <= 5 * 10⁴
1 <= chargeTimes[i], runningCosts[i] <= 10⁵
1 <= budget <= 10¹⁵

lightbulb

解题思路

方法一：双指针 + 单调队列

问题实际上是求滑动窗口内的最大值，可以用单调队列来求解。

我们只需要二分枚举窗口 $k$ 的大小，找到一个最大的 $k$ ，使得满足题目要求。

实现过程中，实际上不需要进行二分枚举，只需要将固定窗口改为双指针非固定窗口即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ，其中 $n$ 是题目中机器人的数目。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def maximumRobots(
        self, chargeTimes: List[int], runningCosts: List[int], budget: int
    ) -> int:
        q = deque()
        ans = s = l = 0
        for r, (t, c) in enumerate(zip(chargeTimes, runningCosts)):
            s += c
            while q and chargeTimes[q[-1]] <= t:
                q.pop()
            q.append(r)
            while q and (r - l + 1) * s + chargeTimes[q[0]] > budget:
                if q[0] == l:
                    q.popleft()
                s -= runningCosts[l]
                l += 1
            ans = max(ans, r - l + 1)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to binary search over possible lengths combined with linear scan per candidate length using sliding window and monotonic queue. Space complexity is O(n) for the monotonic queue and prefix sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if you can calculate subarray maximum efficiently instead of recomputing for every window.
question_mark
Consider using binary search on the number of robots instead of iterating over all possible lengths.
question_mark
Watch out for overflow when multiplying length by sum of running costs.

warning

常见陷阱

外企场景

error
Recomputing max(chargeTimes) for each subarray instead of using a monotonic queue.
error
Failing to handle edge cases where no robot can fit within the budget.
error
Using nested loops for every subarray length leading to TLE on large n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find maximum number of robots with arbitrary non-consecutive selection under budget constraints.
arrow_right_alt
Calculate maximum robots for varying budgets given dynamic charge and running costs.
arrow_right_alt
Minimize total cost for a fixed number of consecutive robots using similar sliding window approach.

help

常见问题

外企场景

继续练习

#862 和至少为 K 的最短子数组 #2528 最大化城市的最小电量 #1687 从仓库到码头运输箱子