力扣刷题之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 。

题干分析

题目解析

      现在我们手里有n个机器人，给定两个长度为n的整数数组：

• chargeTimes：第 iii 个机器人需要的充电时间。
• runningCosts：第 iii 个机器人运行的成本。

还有一个整数budget用来表示我们的预算。

要求 

      找到可以连续运行的最多机器人kmax，使得运行这k个机器人的总开销不超过预算budge。

解题思路

1.滑动窗口法：

• 由于机器人必须连续运行，适合使用滑动窗口来遍历所有可能的连续子数组。
• 窗口的做优边界分别为left和right，初始化都为0。

2.维护窗口内的最大值和总和：

• 最大充电时间：徐璈高效地获取当前窗口内的最大值。
• 使用双端队列来维护窗口内的最大值。
• 而运行成本总和；累加runningCosts，在窗口移动时更新。

3.双端队列维护最大值：

• 双端队列存储窗口内可能成为最大值的元素的下标。
• 保持队列单调递减，即队首始终是当前窗口的最大值。 

4.算法步骤：

初始化

• maxLen = 0：记录满足条件的最大机器人数目。
• left = 0：窗口左边界。
• sumCosts = 0：当前窗口内运行成本的总和。
• deque：用于维护窗口内的最大充电时间。
• front = 0, rear = -1：双端队列的头尾指针。

 遍历数组

对于 right 从 0 到 n-1：

• 扩大窗口：
  • 将当前元素 chargeTimes[right] 维护到 deque 中：
    • 移除 deque 末尾所有小于等于 chargeTimes[right] 的元素。
    • 将 right 加入 deque 末尾。
  • 更新 sumCosts += runningCosts[right]。
• 检查窗口是否满足预算：
  • 计算当前窗口的总开销
  • 如果 totalCost 超过 budget，需要缩小窗口：
    • 如果 deque[front] == left，说明窗口左端的最大值要移出窗口，从 deque 中移除队首。
    • 更新 sumCosts -= runningCosts[left]，移动 left。
  • 重复以上步骤，直到 totalCost 不超过 budget。
• 更新最大长度：
  • 计算当前窗口长度 currentLen = right - left + 1。
  • 如果 currentLen > maxLen，更新 maxLen = currentLen。

5.返回结果

返回maxLen，即在预算内可以连续裕兴的最多机器人数目。 

代码展示 

int maximumRobots(int* chargeTimes, int chargeTimesSize, int* runningCosts, int runningCostsSize, long long budget) {
    typedef long long ll;
    int maxLen = 0;
    int left = 0;
    ll sumCosts = 0;

    // 定义双端队列来维护窗口内的最大 chargeTime
    int deque[chargeTimesSize];
    int front = 0, rear = -1;

    for (int right = 0; right < chargeTimesSize; right++) {
        // 维护双端队列，保持队列中的元素递减
        while (rear >= front && chargeTimes[deque[rear]] <= chargeTimes[right]) {
            rear--;
        }
        deque[++rear] = right;

        // 更新运行成本之和
        sumCosts += runningCosts[right];

        // 检查当前窗口是否满足预算要求
        while (front <= rear) {
            ll totalCost = (ll)chargeTimes[deque[front]] + (right - left + 1) * sumCosts;
            if (totalCost <= budget) {
                break;
            }
            // 移动左指针，调整窗口
            if (deque[front] == left) {
                front++;
            }
            sumCosts -= runningCosts[left];
            left++;
        }

        // 更新最大长度
        int currentLen = right - left + 1;
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
    }

    return maxLen;
}