2398-预算内的最多机器人数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

你有 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 == n
  • 1 <= n <= 5 * 104
  • 1 <= chargeTimes[i], runningCosts[i] <= 105
  • 1 <= budget <= 1015

本题 视频讲解 已出炉，介绍了单调队列的原理，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

前置题目：239. 滑动窗口最大值 。

本题的一种做法是二分答案，这样就转换成了 239 题。

但实际上不用二分，在 239 这题的基础上，把固定大小的滑动窗口改为不固定大小的双指针，具体见代码注释。

更多有关单调队列的题目见我的算法竞赛模板库中的 monotone_queue.go 。

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 chargeTimes 的长度。
  • 空间复杂度：O(n)。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
[sol1-Java]
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(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;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 }

思考题

把「子数组」改成「子序列」要怎么做？

思路和 1383. 最大的团队表现值 是类似的。

思考题的讲解见 视频讲解 的最后一部分，代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maximumRobotsSubseq(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
 Comments
On this page
2398-预算内的最多机器人数目