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

题目描述

这是 LeetCode 上的 2335. 装满杯子需要的最短总时长 ，难度为 简单。

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。

给你一个下标从 0 开始、长度为 3 的整数数组 amount，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。

返回装满所有杯子所需的 最少 秒数。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：amount = [1,4,2]

输出：4

解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯温水。
第 2 秒：装满一杯温水和一杯热水。
第 3 秒：装满一杯温水和一杯热水。
第 4 秒：装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。

示例 2：
1
2
3
4
5
6
7
8
9
10
11
12
输入：amount = [5,4,4]

输出：7

解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯热水。
第 2 秒：装满一杯冷水和一杯温水。
第 3 秒：装满一杯冷水和一杯温水。
第 4 秒：装满一杯温水和一杯热水。
第 5 秒：装满一杯冷水和一杯热水。
第 6 秒：装满一杯冷水和一杯温水。
第 7 秒：装满一杯热水。

示例 3：
1
2
3
4
5
输入：amount = [5,0,0]

输出：5

解释：每秒装满一杯冷水。

提示：

  • $amount.length = 3$
  • $0 <= amount[i] <= 100$

排序 + 递归

水的种类固定为 3，且每种水的数据范围只有 $100$，可直接使用递归进行求解。

为了尽可能的凑成多的对数，我们可以每次取剩余数量最多且不为 0 的两类水进行成组（因此每次处理前需要先对当前 amount 进行排序），直到没有水剩余，或只有一类水的剩余数据量不为 0（剩下的水只能独自生成）。

Java 代码：

1
2
3
4
5
6
7
8
class Solution {
    public int fillCups(int[] amount) {
        Arrays.sort(amount);
        if (amount[1] == 0) return amount[2];
        amount[1]--; amount[2]--;
        return 1 + fillCups(amount);
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int fillCups(vector<int>& amount) {
        sort(amount.begin(), amount.end());
        if (amount[1] == 0) return amount[2];
        amount[1]--; amount[2]--;
        return 1 + fillCups(amount);
    }
};

Python 代码：
1
2
3
4
5
6
7
8
class Solution:
    def fillCups(self, amount: List[int]) -> int:
        amount.sort()
        if amount[1] == 0:
            return amount[2]
        amount[1] -= 1
        amount[2] -= 1
        return 1 + self.fillCups(amount)

TypeScript 代码：
1
2
3
4
5
6
7
function fillCups(amount: number[]): number {
    amount.sort((a, b) => a - b);
    if (amount[1] === 0) return amount[2];
    amount[1] -= 1;
    amount[2] -= 1;
    return 1 + fillCups(amount);
};

  • 时间复杂度：由于 amount 的长度固定为 3，因此排序消耗可视为常量；每次至少会消耗两杯水，直到递归结束或只剩下一种水。复杂度为 $O(\sum_{i = 0}^{2} amount[i])$
  • 空间复杂度：忽略递归和排序带来的额外空间开销，复杂度为 $O(1)$

贪心 + 数学

我们已经知道可以通过「每次取剩余数量最多且不为 0 的水成对」来实现最少生成次数。

那么是否存在直接计算最少生成次数的方法，而不是采用逐回合模拟。

考虑对 amount 进行排序，分别使用 a、b 和 c 代表剩余次数递增的三种种类。

根据 $a + b$ 和 $c$ 的大小关系进行分情况讨论：

  • $a + b \leq c$，此时每消耗一个 $c$ 都可以顺带消除一个 $a$ 或 $b$，因此最少生成次数为 $c$；

  • $a + b > c$，此时考虑其之间的差值 $t = a + b - c$，若能顺利通过 $\frac{t}{2}$ 次对 $a$ 和 $b$ 的合并，可以将局面转成情况一，最少生成次数为 $\frac{t}{2} + c$；

    考虑起始是否能先对 $a$ 和 $b$ 进行 $\frac{t}{2}$ 个回合，由于我们有 $a \leq b$，我们只需考虑是否必然有 $a \geq \frac{t}{2}$ 即可，可通过反证法证明 $a < \frac{t}{2}$ 必然不成立，若有 $a < \frac{t}{2}$，则有 $2a < a + b - c$ => $a < b - c$，由于 $b \leq c$，则有 $a < 0$，与原条件冲突。

    最后，为了处理 $t$ 的奇偶性问题，先用 $a$ 和 $b$ 进行 $\left \lceil \frac{a + b - c}{2} \right \rceil$ 抵消操作，再与 $c$ 进行抵消

Java 代码：

1
2
3
4
5
6
7
8
class Solution {
    public int fillCups(int[] amount) {
        Arrays.sort(amount);
        int a = amount[0], b = amount[1], c = amount[2];
        if (a + b <= c) return c;        
        else return (a + b - c + 1) / 2 + c;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int fillCups(vector<int>& amount) {
        sort(amount.begin(), amount.end());
        int a = amount[0], b = amount[1], c = amount[2];
        if (a + b <= c) return c;
        else return (a + b - c + 1) / 2 + c;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
class Solution:
    def fillCups(self, amount: List[int]) -> int:
        amount.sort()
        a, b, c = amount
        if a + b <= c:
            return c
        else:
            return (a + b - c + 1) // 2 + c

TypeScript 代码：
1
2
3
4
5
6
function fillCups(amount: number[]): number {
    amount.sort((a, b) => a - b);
    const [a, b, c] = amount;
    if (a + b <= c) return c;    
    else return Math.floor((a + b - c + 1) / 2) + c; 
};

  • 时间复杂度：由于 amount 的长度固定为 3，因此排序消耗可视为常量，整体复杂度为 $O(1)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2335 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。