Skip to content

Latest commit

 

History

History
190 lines (156 loc) · 6.06 KB

README_EN.md

File metadata and controls

190 lines (156 loc) · 6.06 KB
comments difficulty edit_url rating source tags
true
Hard
1917
Biweekly Contest 86 Q4
Queue
Array
Binary Search
Prefix Sum
Sliding Window
Heap (Priority Queue)

2398. Maximum Number of Robots Within Budget

中文文档

Description

You have n robots. You are given two 0-indexed integer arrays, chargeTimes and runningCosts, both of length n. The ith 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.

 

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.

 

Constraints:

  • chargeTimes.length == runningCosts.length == n
  • 1 <= n <= 5 * 104
  • 1 <= chargeTimes[i], runningCosts[i] <= 105
  • 1 <= budget <= 1015

Solutions

Solution 1: Two Pointers + Monotonic Queue

The problem is essentially finding the maximum value within a sliding window, which can be solved using a monotonic queue.

We only need to use binary search to enumerate the size of the window $k$, and find the largest $k$ that satisfies the problem requirements.

In the implementation process, we don't actually need to perform binary search enumeration. We just need to change the fixed window to a non-fixed window with double pointers.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the number of robots in the problem.

Python3

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

Java

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        Deque<Integer> q = new ArrayDeque<>();
        int n = chargeTimes.length;
        long s = 0;
        int j = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int a = chargeTimes[i], b = runningCosts[i];
            while (!q.isEmpty() && chargeTimes[q.getLast()] <= a) {
                q.pollLast();
            }
            q.offer(i);
            s += b;
            while (!q.isEmpty() && chargeTimes[q.getFirst()] + (i - j + 1) * s > budget) {
                if (q.getFirst() == j) {
                    q.pollFirst();
                }
                s -= runningCosts[j++];
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        deque<int> q;
        long long s = 0;
        int ans = 0, j = 0, n = chargeTimes.size();
        for (int i = 0; i < n; ++i) {
            int a = chargeTimes[i], b = runningCosts[i];
            while (!q.empty() && chargeTimes[q.back()] <= a) q.pop_back();
            q.push_back(i);
            s += b;
            while (!q.empty() && chargeTimes[q.front()] + (i - j + 1) * s > budget) {
                if (q.front() == j) {
                    q.pop_front();
                }
                s -= runningCosts[j++];
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

Go

func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {
	s := int64(0)
	ans, j := 0, 0
	q := []int{}
	for i, a := range chargeTimes {
		for len(q) > 0 && chargeTimes[q[len(q)-1]] <= a {
			q = q[:len(q)-1]
		}
		q = append(q, i)
		s += int64(runningCosts[i])
		for len(q) > 0 && int64(chargeTimes[q[0]])+int64(i-j+1)*s > budget {
			if q[0] == j {
				q = q[1:]
			}
			s -= int64(runningCosts[j])
			j++
		}
		ans = max(ans, i-j+1)
	}
	return ans
}