Hard

题目描述

你有 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
解释：
可以在预算内运行所有单个机器人或连续的机器人对。
要获得答案 3，考虑前 3 个机器人。总开销为 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24，小于 25。
可以证明无法在预算内连续运行超过 3 个机器人，所以我们返回 3。

示例 2：

输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出：0
解释：即使是单个机器人也会超过预算，所以返回 0。

提示：

  • chargeTimes.length == runningCosts.length == n
  • 1 <= n <= 5 * 10^4
  • 1 <= chargeTimes[i], runningCosts[i] <= 10^5
  • 1 <= budget <= 10^15

解题思路

这道题要求在预算内找到最多能连续运行的机器人数目。成本公式为 max(chargeTimes) + k * sum(runningCosts)，其中 k 是连续机器人的数量。

思路分析：

有两种主要解法：

  1. 二分搜索 + 滑动窗口：二分搜索答案，对于每个候选长度，使用滑动窗口检查是否存在满足预算的连续子数组。需要用单调双端队列维护窗口内的最大充电时间。

  2. 双指针滑动窗口：使用左右指针维护一个有效窗口，右指针扩展窗口，当成本超出预算时左指针收缩窗口。同样需要单调队列维护最大值。

推荐解法：双指针滑动窗口

使用双指针技术更直观，时间复杂度相同但代码更简洁。关键点：

  • 用单调双端队列维护当前窗口的最大充电时间
  • 用前缀和快速计算运行成本之和
  • 当窗口成本超出预算时，移动左指针直到满足条件

单调队列的作用是在 O(1) 时间内获取窗口最大值：队列头部始终保持当前窗口的最大值，队列按下标递增、值递减排列。

代码实现

class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        int n = chargeTimes.size();
        deque<int> dq; // 单调队列维护最大充电时间
        long long sum = 0; // 运行成本之和
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            // 维护单调队列（递减）
            while (!dq.empty() && chargeTimes[dq.back()] <= chargeTimes[right]) {
                dq.pop_back();
            }
            dq.push_back(right);
            sum += runningCosts[right];
            
            // 如果当前窗口超出预算，收缩左边界
            while (left <= right && !dq.empty() && 
                   chargeTimes[dq.front()] + (long long)(right - left + 1) * sum > budget) {
                sum -= runningCosts[left];
                if (dq.front() == left) {
                    dq.pop_front();
                }
                left++;
            }
            
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        from collections import deque
        
        n = len(chargeTimes)
        dq = deque()  # 单调队列维护最大充电时间
        running_sum = 0  # 运行成本之和
        left = 0
        max_len = 0
        
        for right in range(n):
            # 维护单调队列（递减）
            while dq and chargeTimes[dq[-1]] <= chargeTimes[right]:
                dq.pop()
            dq.append(right)
            running_sum += runningCosts[right]
            
            # 如果当前窗口超出预算，收缩左边界
            while left <= right and dq and \
                  chargeTimes[dq[0]] + (right - left + 1) * running_sum > budget:
                running_sum -= runningCosts[left]
                if dq[0] == left:
                    dq.popleft()
                left += 1
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int MaximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.Length;
        var dq = new LinkedList<int>(); // 单调队列维护最大充电时间
        long sum = 0; // 运行成本之和
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            // 维护单调队列（递减）
            while (dq.Count > 0 && chargeTimes[dq.Last.Value] <= chargeTimes[right]) {
                dq.RemoveLast();
            }
            dq.AddLast(right);
            sum += runningCosts[right];
            
            // 如果当前窗口超出预算，收缩左边界
            while (left <= right && dq.Count > 0 && 
                   chargeTimes[dq.First.Value] + (long)(right - left + 1) * sum > budget) {
                sum -= runningCosts[left];
                if (dq.First.Value == left) {
                    dq.RemoveFirst();
                }
                left++;
            }
            
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

var maximumRobots = function(chargeTimes, runningCosts, budget) {
    const n = chargeTimes.length;
    let left = 0;
    let maxRobots = 0;
    let runningSum = 0;
    const deque = [];
    
    for (let right = 0; right < n; right++) {
        runningSum += runningCosts[right];
        
        while (deque.length > 0 && chargeTimes[deque[deque.length - 1]] <= chargeTimes[right]) {
            deque.pop();
        }
        deque.push(right);
        
        while (left <= right && chargeTimes[deque[0]] + (right - left + 1) * runningSum > budget) {
            if (deque[0] === left) {
                deque.shift();
            }
            runningSum -= runningCosts[left];
            left++;
        }
        
        maxRobots = Math.max(maxRobots, right - left + 1);
    }
    
    return maxRobots;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

时间复杂度说明： 每个元素最多进入和离开单调队列一次，所以总体时间复杂度是 O(n)。

空间复杂度说明： 单调队列最多存储 n 个元素，所以空间复杂度是 O(n)。

相关题目