Medium

题目描述

你是一座百年摩天轮的操作员，该摩天轮有四个缆车厢，每个缆车厢最多可以容纳四人。你有能力逆时针旋转缆车厢，每次旋转需要花费 runningCost 美元。

给你一个长度为 n 的数组 customers，其中 customers[i] 表示在第 i 次旋转（从 0 开始计数）之前到达的新顾客数量。这意味着在 customers[i] 个顾客到达之前，你必须旋转摩天轮 i 次。如果缆车厢有空间，你不能让顾客等待。每个顾客在登上距离地面最近的缆车厢时支付 boardingCost 美元，并在该缆车厢再次到达地面时下车。

你可以随时停止摩天轮，包括在服务所有顾客之前。如果你决定停止服务顾客，所有后续的旋转都是免费的，以便让所有顾客安全下车。注意，如果当前有超过四个顾客在摩天轮旁等待，只有四个会登上缆车厢，其余的将等待下一次旋转。

返回使你的利润最大化所需执行的最小旋转次数。如果没有任何情况可以产生正利润，返回 -1。

示例 1：

输入：customers = [8,3], boardingCost = 5, runningCost = 6
输出：3

示例 2：

输入：customers = [10,9,6], boardingCost = 6, runningCost = 4
输出：7

示例 3：

输入：customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92
输出：-1

约束条件：

  • n == customers.length
  • 1 <= n <= 10^5
  • 0 <= customers[i] <= 50
  • 1 <= boardingCost, runningCost <= 100

解题思路

这是一道模拟题，需要我们模拟摩天轮的运转过程。

解题思路：

  1. 模拟过程：我们需要逐步模拟摩天轮的每一次旋转，跟踪等待的顾客数量、已上车的顾客总数和当前利润。

  2. 关键变量：

    • waiting：当前等待的顾客数量
    • totalCustomers：总共上车的顾客数量
    • profit：当前利润
    • maxProfit：最大利润
    • bestRotation：获得最大利润时的旋转次数

  3. 模拟步骤：

    • 处理所有输入的顾客到达时间
    • 每次旋转时，最多4个顾客上车
    • 更新利润 = 上车顾客数 × boardingCost - runningCost
    • 记录最大利润对应的旋转次数

  4. 继续旋转的条件：即使处理完所有输入顾客，如果还有等待的顾客，需要继续旋转。但要注意，如果每次旋转的收益（4 × boardingCost - runningCost）为负，就不应该继续。

  5. 优化点：当等待顾客数量不足4人且继续旋转会亏损时，应该停止模拟。

这个问题的核心是要找到利润最大化的旋转次数，需要考虑所有可能的停止点。

代码实现

class Solution {
public:
    int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
        int waiting = 0;
        int totalCustomers = 0;
        int profit = 0;
        int maxProfit = 0;
        int bestRotation = -1;
        int rotation = 0;
        
        // 处理所有顾客到达的时间点
        for (int i = 0; i < customers.size(); i++) {
            waiting += customers[i];
            
            // 每次旋转最多4人上车
            int boarding = min(waiting, 4);
            waiting -= boarding;
            totalCustomers += boarding;
            
            // 计算利润
            profit = totalCustomers * boardingCost - (i + 1) * runningCost;
            
            if (profit > maxProfit) {
                maxProfit = profit;
                bestRotation = i + 1;
            }
        }
        
        // 继续处理剩余等待的顾客
        while (waiting > 0) {
            rotation++;
            int boarding = min(waiting, 4);
            waiting -= boarding;
            totalCustomers += boarding;
            
            profit = totalCustomers * boardingCost - (customers.size() + rotation) * runningCost;
            
            if (profit > maxProfit) {
                maxProfit = profit;
                bestRotation = customers.size() + rotation;
            }
            
            // 如果继续旋转只会亏损，提前结束
            if (4 * boardingCost < runningCost) {
                break;
            }
        }
        
        return bestRotation;
    }
};

class Solution:
    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:
        waiting = 0
        total_customers = 0
        profit = 0
        max_profit = 0
        best_rotation = -1
        rotation = 0
        
        # 处理所有顾客到达的时间点
        for i in range(len(customers)):
            waiting += customers[i]
            
            # 每次旋转最多4人上车
            boarding = min(waiting, 4)
            waiting -= boarding
            total_customers += boarding
            
            # 计算利润
            profit = total_customers * boardingCost - (i + 1) * runningCost
            
            if profit > max_profit:
                max_profit = profit
                best_rotation = i + 1
        
        # 继续处理剩余等待的顾客
        while waiting > 0:
            rotation += 1
            boarding = min(waiting, 4)
            waiting -= boarding
            total_customers += boarding
            
            profit = total_customers * boardingCost - (len(customers) + rotation) * runningCost
            
            if profit > max_profit:
                max_profit = profit
                best_rotation = len(customers) + rotation
            
            # 如果继续旋转只会亏损，提前结束
            if 4 * boardingCost < runningCost:
                break
        
        return best_rotation

public class Solution {
    public int MinOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        int waiting = 0;
        int totalCustomers = 0;
        int profit = 0;
        int maxProfit = 0;
        int bestRotation = -1;
        int rotation = 0;
        
        // 处理所有顾客到达的时间点
        for (int i = 0; i < customers.Length; i++) {
            waiting += customers[i];
            
            // 每次旋转最多4人上车
            int boarding = Math.Min(waiting, 4);
            waiting -= boarding;
            totalCustomers += boarding;
            
            // 计算利润
            profit = totalCustomers * boardingCost - (i + 1) * runningCost;
            
            if (profit > maxProfit) {
                maxProfit = profit;
                bestRotation = i + 1;
            }
        }
        
        // 继续处理剩余等待的顾客
        while (waiting > 0) {
            rotation++;
            int boarding = Math.Min(waiting, 4);
            waiting -= boarding;
            totalCustomers += boarding;
            
            profit = totalCustomers * boardingCost - (customers.Length + rotation) * runningCost;
            
            if (profit > maxProfit) {
                maxProfit = profit;
                bestRotation = customers.Length + rotation;
            }
            
            // 如果继续旋转只会亏损，提前结束
            if (4 * boardingCost < runningCost) {
                break;
            }
        }
        
        return bestRotation;
    }
}

var minOperationsMaxProfit = function(customers, boardingCost, runningCost) {
    let waiting = 0;
    let totalCustomers = 0;
    let profit = 0;
    let maxProfit = 0;
    let bestRotation = -1;
    let rotation = 0;
    
    // 处理所有顾客到达的时间点
    for (let i = 0; i < customers.length; i++) {
        waiting += customers[i];
        
        // 每次旋转最多4人上车
        const boarding = Math.min(waiting, 4);
        waiting -= boarding;
        totalCustomers += boarding;
        
        // 计算利润
        profit = totalCustomers * boardingCost - (i + 1) * runningCost;
        
        if (profit > maxProfit) {
            maxProfit = profit;
            bestRotation = i + 1;
        }
    }
    
    // 继续处理剩余等待的顾客
    while (waiting > 0) {
        rotation++;
        const boarding = Math.min(waiting, 4);
        waiting -= boarding;
        totalCustomers += boarding;
        
        profit = totalCustomers * boardingCost - (customers.length + rotation) * runningCost;
        
        if (profit > maxProfit) {
            maxProfit = profit;
            bestRotation = customers.length + rotation;
        }
        
        // 如果继续旋转只会亏损，提前结束
        if (4 * boardingCost < runningCost) {
            break;
        }
    }
    
    return bestRotation;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + w/4)，其中 n 是 customers 数组长度，w 是最大等待人数。由于每个顾客最多等待 50 人，最坏情况是 O(n + 50n/4) = O(n)
空间复杂度O(1)，只使用了常数个变量存储状态