预算内的最多机器人数目

难度:

标签:

题目描述

代码结果

运行时间: 166 ms, 内存: 21.9 MB

/*
 题目思路：
 使用Java Stream API实现最大连续机器人数的计算。主要思路与Java版本相同，只是使用Stream来计算总运行成本和最大充电时间。
 */

import java.util.*;
import java.util.stream.*;

public int maxRobotsStream(int[] chargeTimes, int[] runningCosts, long budget) {
    int n = chargeTimes.length;
    int left = 0, right = 0;
    long sumRunningCosts = 0;
    int maxRobots = 0;

    while (right < n) {
        // 计算总运行成本
        sumRunningCosts += runningCosts[right];
        
        // 计算当前窗口中的最大充电时间
        int finalRight = right;
        int maxChargeTime = IntStream.range(left, right + 1)
            .map(i -> chargeTimes[i])
            .max()
            .getAsInt();

        // 计算当前窗口的总成本
        long totalCost = maxChargeTime + (right - left + 1) * sumRunningCosts;

        // 如果总成本超出预算，移动左指针，缩小窗口
        while (totalCost > budget && left <= right) {
            sumRunningCosts -= runningCosts[left];
            left++;
            maxChargeTime = IntStream.range(left, right + 1)
                .map(i -> chargeTimes[i])
                .max()
                .getAsInt();
            totalCost = maxChargeTime + (right - left + 1) * sumRunningCosts;
        }

        // 更新最大连续运行的机器人数
        maxRobots = Math.max(maxRobots, right - left + 1);
        right++;
    }

    return maxRobots;
}

解释

方法:

The solution uses a sliding window approach combined with a deque to maintain the maximum charge time within the current window. As we iterate through the robots using a right pointer, we add the current robot's charge time to the deque in a way that ensures the deque is always sorted in descending order. This allows the largest element (maximum charge time) to always be at the front of the deque. We also keep a running sum of the running costs. At each step, we check if the sum of the maximum charge time and the product of the number of robots and the sum of running costs fits within the budget. If it does, we update our answer. If it doesn't, we adjust the window by moving the left pointer to the right, ensuring the properties of the deque and updating the running costs sum accordingly.

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在滑动窗口调整左指针时，直接检查deque的首元素与chargeTimes[left]是否相等来决定是否出队，这种做法是否总是正确的？存在哪些潜在风险？

▷

这种做法是正确的，因为deque中只存储了当前滑动窗口内的元素，并且是按照其值的降序来存储的。当左指针left向右移动时，只有当deque的首元素等于chargeTimes[left]时，表示当前窗口的最大充电时间是由即将被移出窗口的元素提供的，因此需要将其从deque中移除。潜在的风险是如果未正确维护deque，即在其他操作中使deque状态与当前窗口状态不同步，那么这种直接检查的方法可能会导致错误。但在题解中的实现方式是正确且安全的，因为每次操作都确保了deque与窗口的同步。

🦆

如果数组chargeTimes中存在重复的最大值，当前的解决方案如何处理？解决方案是否能正确地从deque中移除对应元素？

▷

当前解决方案能够正确处理chargeTimes中存在重复的最大值的情况。在deque中添加新元素时，如果新元素大于或等于deque中的元素，那么较小的元素会被移除，直到找到一个更大的元素或者deque为空。这保证了即使有重复的最大值，每个元素也只会在它属于当前窗口的最大值时才会处于deque的首位。在移动左指针时，只有当deque的首元素等于即将移出窗口的chargeTimes[left]时才会被移除，这确保了即使存在重复的最大值，也只有正确的元素会被移除。

🦆

在计算当前窗口是否符合预算条件时，公式直接使用了`(right - left + 1) * costs`来计算总运行成本，这里的costs变量是否正确地表示了窗口内机器人的运行成本之和？

▷

在题解中，`costs`变量被用来累加从left到right的所有机器人的运行成本，因此它确实正确地表示了当前滑动窗口内所有机器人的运行成本之和。每次右指针right向右移动时，当前机器人的运行成本被加到`costs`上，如果窗口不符合预算条件，左指针left会向右移动并从`costs`中减去相应的运行成本。这保证了`costs`始终反映了当前窗口内机器人的总运行成本。因此，使用`(right - left + 1) * costs`来计算总运行成本是不正确的，应该直接使用`costs`，因为`costs`已经是总和，不需要再乘以机器人数量。

预算内的最多机器人数目

题目描述

代码结果

解释

代码细节讲解

相关问题