Maximum Number of Robots Within Budget

A mono deque can be used to maintain the maximum value in a sliding window. A mono deque is a double-ended queue where the elements are stored in a specific order (either increasing or decreasing). In this case, we’ll use a decreasing mono deque to store the indices of the elements in a sliding window in such a way that the maximum value is always at the front of the deque.

Here’s how you can apply a mono deque to the given problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import deque

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        n = len(chargeTimes)
        max_robots = 0
        running_cost_sum = 0
        total_cost = 0

        # Initialize a mono deque to store the indices of chargeTimes
        mono_deque = deque()

        # Iterate through the robots
        for i in range(n):
            # Add the current running cost
            running_cost_sum += runningCosts[i]

            # Update the deque for the current charge time
            while mono_deque and chargeTimes[i] >= chargeTimes[mono_deque[-1]]:
                mono_deque.pop()
            mono_deque.append(i)

            # Check if the window size exceeds the count of consecutive robots
            while i - mono_deque[0] + 1 > max_robots + 1:
                mono_deque.popleft()

            # Calculate the total cost for the current number of robots
            total_cost = chargeTimes[mono_deque[0]] + (max_robots + 1) * running_cost_sum

            # Check if the total cost is within budget
            if total_cost <= budget:
                max_robots += 1
            else:
                running_cost_sum -= runningCosts[i - max_robots]

        return max_robots

Here, mono_deque stores the indices of the chargeTimes array in a way that the maximum value of the current window is always at the front. By maintaining the window size based on the number of consecutive robots, we can efficiently find the maximum number of consecutive robots that can be run without exceeding the given budget.