class Solution {
public:
int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
}
};
2398. 预算内的最多机器人数目
你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。
请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。
示例 1：
输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25 输出：3 解释： 可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。 选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。 可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。
示例 2：
输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19 输出：0 解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。
提示：
chargeTimes.length == runningCosts.length == n1 <= n <= 5 * 1041 <= chargeTimes[i], runningCosts[i] <= 1051 <= budget <= 1015原站题解
rust 解法, 执行用时: 27 ms, 内存消耗: 3 MB, 提交时间: 2024-09-13 09:10:30
use std::collections::VecDeque;
impl Solution {
pub fn maximum_robots(charge_times: Vec<i32>, running_costs: Vec<i32>, budget: i64) -> i32 {
let mut ans = 0;
let mut left = 0;
let mut sum = 0i64;
let mut q = VecDeque::new();
for right in 0..charge_times.len() {
// 1. 入
while !q.is_empty() && charge_times[right] >= charge_times[*q.back().unwrap()] {
q.pop_back();
}
q.push_back(right);
sum += running_costs[right] as i64;
// 2. 出
while !q.is_empty() && charge_times[*q.front().unwrap()] as i64 + (right - left + 1) as i64 * sum > budget {
if *q.front().unwrap() == left {
q.pop_front();
}
sum -= running_costs[left] as i64;
left += 1;
}
// 3. 更新答案
ans = ans.max(right - left + 1);
}
ans as _
}
}
javascript 解法, 执行用时: 128 ms, 内存消耗: 62.2 MB, 提交时间: 2024-09-13 09:10:06
/**
* @param {number[]} chargeTimes
* @param {number[]} runningCosts
* @param {number} budget
* @return {number}
*/
var maximumRobots = function(chargeTimes, runningCosts, budget) {
let ans = 0, left = 0, sum = 0;
const q = Array(chargeTimes.length);
let head = 0, tail = 0; // 队头和队尾
for (let right = 0; right < chargeTimes.length; right++) {
// 1. 入
while (head < tail && chargeTimes[right] >= chargeTimes[q[tail - 1]]) {
tail--;
}
q[tail++] = right;
sum += runningCosts[right];
// 2. 出
while (head < tail && chargeTimes[q[head]] + (right - left + 1) * sum > budget) {
if (q[head] === left) {
head++;
}
sum -= runningCosts[left++];
}
// 3. 更新答案
ans = Math.max(ans, right - left + 1);
}
return ans;
};
python3 解法, 执行用时: 312 ms, 内存消耗: 22.5 MB, 提交时间: 2023-06-17 09:23:17
class Solution:
def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
n = len(chargeTimes)
ans = 0
q = deque() # 严格单调递减队列维护窗口内chargeTimes的最大值
tot = 0 # 维护窗口内runningCosts的子数组和
k = 0 # 维护窗口长度
for i in range(n):
# 判断队列单调性，队尾出队
while q and chargeTimes[q[-1]] <= chargeTimes[i]:
q.pop()
# 增大窗口，队尾入队
q.append(i)
tot += runningCosts[i]
k += 1
# 判断是否满足条件，队首出队
while q and chargeTimes[q[0]] + k * tot > budget:
k -= 1
tot -= runningCosts[i - k]
if q[0] == i - k:
q.popleft()
ans = max(ans, k)
return ans
'''
# 子数组改成子序列的解法
class Solution:
def maximumRobotsSeque(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
ans = sum_cost = 0
h = [] # 最大堆，堆顶表示当前的最大花费，从而贪心地在不满足要求的情况下，优先去掉最大的花费
for t, c in sorted(zip(chargeTimes, runningCosts)): # 按照时间排序，从而保证当前的时间是最大的，在此之前的机器人都是可以选的
heappush(h, -c)
sum_cost += c
while h and t + len(h) * sum_cost > budget:
sum_cost += heappop(h) # 弹出一个最大花费，即使弹出的是当前的 c 也没关系，这不会得到更大的 ans
ans = max(ans, len(h))
return ans
'''
golang 解法, 执行用时: 128 ms, 内存消耗: 7.7 MB, 提交时间: 2023-06-17 09:21:18
func maximumRobots(chargeTimes, runningCosts []int, budget int64) (ans int) {
sum, left, q := int64(0), 0, []int{}
// 枚举区间右端点 right，计算区间左端点 left 的最小值
for right, t := range chargeTimes {
// 及时清除队列中的无用数据，保证队列的单调性
for len(q) > 0 && t >= chargeTimes[q[len(q)-1]] {
q = q[:len(q)-1]
}
q = append(q, right)
sum += int64(runningCosts[right])
// 如果左端点 left 不满足要求，就不断右移 left
for len(q) > 0 && int64(chargeTimes[q[0]])+int64(right-left+1)*sum > budget {
// 及时清除队列中的无用数据，保证队列的单调性
if q[0] == left {
q = q[1:]
}
sum -= int64(runningCosts[left])
left++
}
ans = max(ans, right-left+1)
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 180 ms, 内存消耗: 106.1 MB, 提交时间: 2023-06-17 09:20:44
class Solution {
public:
int maximumRobots(vector<int> &chargeTimes, vector<int> &runningCosts, long long budget) {
int ans = 0;
deque<int> q;
long sum = 0L;
// 枚举区间右端点 right，计算区间左端点 left 的最小值
for (int left = 0, right = 0; right < chargeTimes.size(); ++right) {
// 及时清除队列中的无用数据，保证队列的单调性
while (!q.empty() && chargeTimes[right] >= chargeTimes[q.back()])
q.pop_back();
q.push_back(right);
sum += runningCosts[right];
// 如果左端点 left 不满足要求，就不断右移 left
while (!q.empty() && chargeTimes[q.front()] + (right - left + 1) * sum > budget) {
// 及时清除队列中的无用数据，保证队列的单调性
if (q.front() == left) q.pop_front();
sum -= runningCosts[left++];
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
java 解法, 执行用时: 21 ms, 内存消耗: 52.8 MB, 提交时间: 2023-06-17 09:20:32
class Solution {
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
var ans = 0;
var q = new ArrayDeque<Integer>();
var sum = 0L;
// 枚举区间右端点 right，计算区间左端点 left 的最小值
for (int left = 0, right = 0; right < chargeTimes.length; ++right) {
// 及时清除队列中的无用数据，保证队列的单调性
while (!q.isEmpty() && chargeTimes[right] >= chargeTimes[q.peekLast()])
q.pollLast();
q.addLast(right);
sum += runningCosts[right];
// 如果左端点 left 不满足要求，就不断右移 left
while (!q.isEmpty() && chargeTimes[q.peekFirst()] + (right - left + 1) * sum > budget) {
// 及时清除队列中的无用数据，保证队列的单调性
if (q.peekFirst() == left) q.pollFirst();
sum -= runningCosts[left++];
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
python3 解法, 执行用时: 344 ms, 内存消耗: 22.1 MB, 提交时间: 2023-06-17 09:20:19
# 双指针 + 单调队列
class Solution:
def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
ans = s = left = 0
q = deque()
# 枚举区间右端点 right，计算区间左端点 left 的最小值
for right, (t, c) in enumerate(zip(chargeTimes, runningCosts)):
# 及时清除队列中的无用数据，保证队列的单调性
while q and t >= chargeTimes[q[-1]]:
q.pop()
q.append(right)
s += c
# 如果左端点 left 不满足要求，就不断右移 left
while q and chargeTimes[q[0]] + (right - left + 1) * s > budget:
# 及时清除队列中的无用数据，保证队列的单调性
if q[0] == left:
q.popleft()
s -= runningCosts[left]
left += 1
ans = max(ans, right - left + 1)
return ans