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 long cost = 0;
    deque<int> dq;  // max queue storing 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 (!dq.empty() && dq.back() < chargeTimes[i])
        dq.pop_back();
      dq.push_back(chargeTimes[i]);
      if (dq.front() + (i - j + 1) * cost > budget) {
        if (dq.front() == chargeTimes[j])
          dq.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;
    // max queue storing chargeTimes[i]
    Deque<Integer> dq = 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 (!dq.isEmpty() && dq.peekLast() < chargeTimes[i])
        dq.pollLast();
      dq.offerLast(chargeTimes[i]);
      if (dq.peekFirst() + (i - j + 1) * cost > budget) {
        if (dq.peekFirst() == chargeTimes[j])
          dq.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
    dq = collections.deque()  # max queue storing 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 dq and dq[-1] < chargeTime:
        dq.pop()
      dq.append(chargeTime)
      if dq[0] + (i - j + 1) * cost > budget:
        if dq[0] == chargeTimes[j]:
          dq.popleft()
        cost -= runningCosts[j]
        j += 1

    return len(chargeTimes) - j