---

1599. 经营摩天轮的最大利润

• 标签：数组、模拟
• 难度：中等

题目链接

• 1599. 经营摩天轮的最大利润 - 力扣

题目大意

描述：经营一个摩天轮，有 $4$ 个座舱，每个座舱最多容纳 $4$ 位游客。每个游客登舱时支付 $boardingCost$ 美元，转动一次摩天轮的成本是 $runningCost$ 美元。

给定数组 $customers$ 表示每分钟到达的游客数。每分钟的操作流程：

1. 等待队列中的游客数增加 $customers[i]$。
2. 让最多 $4$ 位游客登舱（直到座舱满或队列空）。
3. 转动摩天轮。

要求：返回使得利润最大的最早转动次数（从 $1$ 开始计数）。如果全程利润都不为正，返回 $-1$。

说明：

• $1 \le customers.length \le 10^5$。
• $0 \le customers[i] \le 200$。
• $1 \le boardingCost, runningCost \le 100$。

示例：

• 示例 1：

输入：customers = [8,3], boardingCost = 5, runningCost = 6
输出：3
解释：座舱上标注的数字是该座舱的当前游客数。
1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4 * $5 - 1 * $6 = $14 。
2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8 * $5 - 2 * $6 = $28 。
3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11 * $5 - 3 * $6 = $37 。
轮转 3 次得到最大利润，最大利润为 $37 。

• 示例 2：

输入：customers = [10,9,6], boardingCost = 6, runningCost = 4
输出：7
解释：
1. 10 位游客抵达，4 位登舱，6 位等待下一舱，摩天轮轮转。当前利润为 4 * $6 - 1 * $4 = $20 。
2. 9 位游客抵达，4 位登舱，11 位等待（2 位是先前就在等待的，9 位新加入等待的），摩天轮轮转。当前利润为 8 * $6 - 2 * $4 = $40 。
3. 最后 6 位游客抵达，4 位登舱，13 位等待，摩天轮轮转。当前利润为 12 * $6 - 3 * $4 = $60 。
4. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 * $6 - 4 * $4 = $80 。
5. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 20 * $6 - 5 * $4 = $100 。
6. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 24 * $6 - 6 * $4 = $120 。
7. 1 位登舱，摩天轮轮转。当前利润为 25 * $6 - 7 * $4 = $122 。
轮转 7 次得到最大利润，最大利润为$122 。

解题思路

思路 1：模拟

1. 核心思想

模拟每分钟的操作过程：接待游客、登舱、转动、计算利润。记录最大利润对应的转动次数。

注意：即使 $customers$ 数组遍历完，只要队列中还有等待的游客，就要继续转动直到所有游客都完成。

2. 具体步骤

第 1 步：初始化 $wait = 0$（等待人数），$profit = 0$（当前利润），$max\_profit = 0$（最大利润），$ans = -1$，$rotate = 0$（转动次数）。

第 2 步：用 $i$ 遍历 $customers$：

• $wait += customers[i]$。
• $board = min(wait, 4)$，$wait -= board$。
• $profit += board \times boardingCost - runningCost$。
• $rotate += 1$。
• 如果 $profit > max\_profit$：$max\_profit = profit$，$ans = rotate$。

第 3 步：当 $wait > 0$ 时继续：

• $board = min(wait, 4)$，$wait -= board$。
• $profit += board \times boardingCost - runningCost$。
• $rotate += 1$。
• 如果 $profit > max\_profit$：$max\_profit = profit$，$ans = rotate$。

第 4 步：返回 $ans$。

3. 举例说明

以 $customers = [8,3], boardingCost = 5, runningCost = 6$ 为例：

• $i=0$：$wait=8$，$board=4$，$wait=4$，$profit=4\times5-6=14$，$rotate=1$，$max\_profit=14$，$ans=1$。
• $i=1$：$wait=4+3=7$，$board=4$，$wait=3$，$profit=14+14=28$，$rotate=2$，$max\_profit=28$，$ans=2$。
• 剩余：$board=3$，$wait=0$，$profit=28+3\times5-6=37$，$rotate=3$，$max\_profit=37$，$ans=3$。

返回 $3$。

以 $customers = [0,0,0], boardingCost = 5, runningCost = 10$ 为例：

• 每转动一次利润 $-10$，全程亏损，返回 $-1$。

思路 1：代码

class Solution:
    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:
        wait = 0
        profit = 0
        max_profit = 0
        ans = -1
        rotate = 0
        i = 0
        n = len(customers)

        while i < n or wait > 0:
            if i < n:
                wait += customers[i]
                i += 1
            board = min(wait, 4)
            wait -= board
            profit += board * boardingCost - runningCost
            rotate += 1
            if profit > max_profit:
                max_profit = profit
                ans = rotate

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(\max(n, total/4))$，$total$ 为游客总数。
• 空间复杂度：$O(1)$。