Published: Sep 21, 2022

## Introduction

This is a type of problem which uses subarray’s minimum or maximum to calculate some value. For such type, a monotonic stack is a good data structure to solve the problem. The stack saves indices to make the stack monotonically increasing or decreasing. As for this problem, the monotonically decreasing stack is used to save indices. Also, this problem uses a sliding window to calculate a value.

## Problem Description

You have

`n`

robots. You are given two 0-indexed integer arrays,`chargeTimes`

and`runningCosts`

, both of length`n`

. The i-th robot costs`chargeTimes[i]`

units to charge and costs`runningCosts[i]`

units to run. You are also given an integer`budget`

. The total cost of running`k`

chosen robots is equal to`max(chargeTimes) + k * sum(runningCosts)`

, where`max(chargeTimes)`

is the largest charge cost among the`k`

robots and`sum(runningCosts)`

is the sum of running costs among the`k`

robots.Return the maximum number of consecutive robots you can run such that the total cost does not exceed budget.

Constraints:

`chargeTimes.length == runningCosts.length == n`

`1 <= n <= 5 * 10**4`

`1 <= chargeTimes[i], runningCosts[i] <= 10**5`

`1 <= budget <= 10**15`

https://leetcode.com/problems/maximum-number-of-robots-within-budget/

## Examples

```
Example 1
Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
Output: 3
Explanation:
It is possible to run all individual and consecutive pairs of robots within budget.
To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25.
It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.
```

```
Example 2
Input: chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
Output: 0
Explanation: No robot can be run that does not exceed the budget, so we return 0.
```

## Analysis

The sliding window starts from 0 and 0 as left and right. The right pointer shifts using the monotonic stack to find a next bigger value’s index. The stack’s index 0 has the index of maximum value between left and right pointers. The range sum is calculated by subtracting left value and adding right value. This makes easy to calculate max(chargeTimes) + k * sum(runningCosts). The final answer is a length of subarray, so right - left + 1 is compared to the maximum so far.

## Solution

```
class MaximumNumberOfRobotsWithinBudget:
def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
left, right, stack, n = 0, 0, [], len(chargeTimes)
cur_sum, result = 0, 0
while left < n:
for next_r in range(right, n):
while stack and chargeTimes[stack[-1]] < chargeTimes[next_r]:
stack.pop()
stack.append(next_r)
while stack and stack[0] < left:
stack.pop(0)
cur_max = chargeTimes[stack[0]]
cur_sum += runningCosts[next_r]
if cur_max + (next_r - left + 1) * cur_sum > budget:
break
else:
result = max(result, next_r - left + 1)
cur_sum -= runningCosts[left]
left += 1
right = next_r + 1
return result
```

## Complexities

- Time:
`O(n^2)`

- Space:
`O(n)`