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

1、题干

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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

2、思路

假设杯子数量从少到多分别为 min、mid、max，首先得装满最多的杯子，因此存在两种情况：

• min + mid <= max，这种情况只需要 max 秒钟就能装满所有杯子
• min + mid > max，先装满最多的杯子，需要 max 秒钟
  • 另外两种杯子会剩余 min + mid - max 个，剩余杯子可能为奇数也可能为偶数，但两种杯子差值最多为 1，所以还需要 Math.ceil((mid + min - max) / 2) 秒钟

3、代码

function fillCups(amount: number[]): number {
    const [min, mid, max] = amount.sort((a, b) => a - b);
    if (min + mid <= max) return max;
    return max + Math.ceil((mid + min - max) / 2);
};

4、复杂度

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

5、执行结果