装满杯子需要的最短总时长

难度: Easy

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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 == 3
0 <= amount[i] <= 100

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        #思路:贪心:不断地打数量排前二的水
        result=0
        while amount!=[0,0,0]:
            amount.sort(reverse=True)
            amount[0]-=1
            if amount[1]!=0:
                amount[1]-=1
            result+=1
        return result

Explain

该题解采用贪心算法的思路。在每一步中，算法首先将数组排序，确保数量最多的杯子类型在前面。然后，每秒钟尽可能装满两种不同类型的水：首先装满最多的那种水一杯，如果第二多的那种水还有剩余，再装满一杯。这个过程不断重复，直到所有的杯子都被装满。这样做可以最大化每一秒的效率，从而达到最短的总时间。

时间复杂度: O(max(amount))

空间复杂度: O(1)

class Solution:
    def fillCups(self, amount: List[int]) -> int:
        # 思路: 贪心算法, 不断地填装数量排前两位的水
        result = 0  # 初始化结果变量，用来计数需要的秒数
        while amount != [0, 0, 0]:  # 继续循环直到所有类型的杯子都填满
            amount.sort(reverse=True)  # 降序排序，使得数量最多的杯子类型排在前面
            amount[0] -= 1  # 装满一杯最多的水
            if amount[1] != 0:  # 如果第二多的水还有剩余
                amount[1] -= 1  # 也装满一杯
            result += 1  # 每装满一次，秒数加一
        return result  # 返回所需的最短秒数

Explore

贪心算法在此问题中有效，因为每秒尽可能多地装满杯子是减少总时间的直接方法。问题的目标是最小化总时间，而每次操作都尽可能最大化填充的杯子数量（每次两个），就能保证在任何给定的瞬间都在尽可能地减少剩余的总杯子数。由于每个杯子的填充耗时相同，所以没有特殊情况使得贪心算法无法产生最优解。该问题确保了每次贪心选择都是全局最优的一部分，因此总能达到最优解。

在某种类型的杯子数量远大于其他两种的情况下，这种结束条件依然是有效和最优的。因为贪心算法保证了每一秒都尽可能多地填满杯子，当最多数量的杯子类型仍然剩余时，算法会继续填充该类型的杯子。因此，即使某一类型的杯子数量远大于其他两种，算法仍然会持续工作直到所有杯子都填满，并且其他类型的杯子先被填满了，也不会影响到总时间的最小化。

在这个特定问题中，考虑当前数量最多的两种水并不会错过全局最优解。这是因为目标是尽快填满所有杯子，而每次选择数量最多的两种水进行填充是达到这个目标的最快方法。局部最优解（每次填充最多可能的杯子数量）在这种情况下直接贡献到全局最优解（最短总时间）。因此，这种策略是恰当的，并且能够确保全局最优。

代码中实际上有处理这个边界情况的逻辑。在减1之前，代码检查了`amount[1]`是否不为0。这个条件检查确保了只有当`amount[1]`大于0时，才会减去1。因此，该算法考虑了`amount[1]`可能为0的边界情况，避免了进行无效的减1操作，这是正确和安全的处理方式。