Skip to content

2398. Maximum Number of Robots Within Budget 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts,
                    long long budget) {
    long cost = 0;
    deque<int> maxQ;  // Stores `chargeTimes[i]`.

    int j = 0;  // window's range := [i..j], so k = i - j + 1
    for (int i = 0; i < chargeTimes.size(); ++i) {
      cost += runningCosts[i];
      while (!maxQ.empty() && maxQ.back() < chargeTimes[i])
        maxQ.pop_back();
      maxQ.push_back(chargeTimes[i]);
      if (maxQ.front() + (i - j + 1) * cost > budget) {
        if (maxQ.front() == chargeTimes[j])
          maxQ.pop_front();
        cost -= runningCosts[j++];
      }
    }

    return chargeTimes.size() - j;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
    long cost = 0;
    // Stores `chargeTimes[i]`.
    Deque<Integer> maxQ = new ArrayDeque<>();

    int j = 0; // window's range := [i..j], so k = i - j + 1
    for (int i = 0; i < chargeTimes.length; ++i) {
      cost += runningCosts[i];
      while (!maxQ.isEmpty() && maxQ.peekLast() < chargeTimes[i])
        maxQ.pollLast();
      maxQ.offerLast(chargeTimes[i]);
      if (maxQ.peekFirst() + (i - j + 1) * cost > budget) {
        if (maxQ.peekFirst() == chargeTimes[j])
          maxQ.pollFirst();
        cost -= runningCosts[j++];
      }
    }

    return chargeTimes.length - j;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
    cost = 0
    maxQ = collections.deque()  # Stores `chargeTimes[i]`.

    j = 0  # window's range := [i..j], so k = i - j + 1
    for i, (chargeTime, runningCost) in enumerate(zip(chargeTimes, runningCosts)):
      cost += runningCost
      while maxQ and maxQ[-1] < chargeTime:
        maxQ.pop()
      maxQ.append(chargeTime)
      if maxQ[0] + (i - j + 1) * cost > budget:
        if maxQ[0] == chargeTimes[j]:
          maxQ.popleft()
        cost -= runningCosts[j]
        j += 1

    return len(chargeTimes) - j