LeetCode 题解工作台
装满杯子需要的最短总时长
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。 给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0] 、 amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们可以每次贪心地选择其中较大的两个数进行减一操作（最多减为 ），直至所有数变为 。 时间复杂度 ，空间复杂度 。其中 为数组 `amount` 中所有数的和，本题中 $S \leq 300$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
示例 1：
输入：amount = [1,4,2] 输出：4 解释：下面给出一种方案： 第 1 秒：装满一杯冷水和一杯温水。 第 2 秒：装满一杯温水和一杯热水。 第 3 秒：装满一杯温水和一杯热水。 第 4 秒：装满一杯温水。 可以证明最少需要 4 秒才能装满所有杯子。
示例 2：
输入：amount = [5,4,4] 输出：7 解释：下面给出一种方案： 第 1 秒：装满一杯冷水和一杯热水。 第 2 秒：装满一杯冷水和一杯温水。 第 3 秒：装满一杯冷水和一杯温水。 第 4 秒：装满一杯温水和一杯热水。 第 5 秒：装满一杯冷水和一杯热水。 第 6 秒：装满一杯冷水和一杯温水。 第 7 秒：装满一杯热水。
示例 3：
输入：amount = [5,0,0] 输出：5 解释：每秒装满一杯冷水。
提示：
amount.length == 30 <= amount[i] <= 100
解题思路
方法一：贪心 + 排序
我们可以每次贪心地选择其中较大的两个数进行减一操作（最多减为 ），直至所有数变为 。
时间复杂度 ，空间复杂度 。其中 为数组 amount 中所有数的和，本题中 。
class Solution:
def fillCups(self, amount: List[int]) -> int:
ans = 0
while sum(amount):
amount.sort()
ans += 1
amount[2] -= 1
amount[1] = max(0, amount[1] - 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(1) with fixed-length arrays since operations involve only three elements, or O(n log n) if generalized with a heap. Space complexity is O(1) for in-place operations or O(n) if a heap is used. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Consider the effect of filling two different types each second versus one type.
- question_mark
Think about whether the largest cup count ever dictates the minimum total time.
- question_mark
Watch for off-by-one errors when decrementing cup counts each second.
常见陷阱
外企场景- error
Attempting to fill cups in arbitrary order without maximizing each second wastes time.
- error
Failing to check that the largest cup type does not exceed half of remaining cups may yield incorrect results.
- error
Neglecting to handle cases where only one type remains can miscount total seconds.
进阶变体
外企场景- arrow_right_alt
Generalize to more than three cup types, requiring priority queues to select the largest pair each second.
- arrow_right_alt
Allow filling up to k cups per second if types are distinct, adjusting the greedy selection accordingly.
- arrow_right_alt
Introduce unequal fill rates for each type, requiring weighted greedy selection to minimize total time.