【面试高频题】难度 1/5，可灵活切换数据范围的小小思维题
题目描述
这是 LeetCode 上的 2335. 装满杯子需要的最短总时长 ，难度为 简单。
Tag : 「排序」、「递归」、「模拟」、「贪心」、「数学」
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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=3amount.length = 3amount.length=3
- 0<=amount[i]<=1000 <= amount[i] <= 1000<=amount[i]<=100
排序 + 递归
水的种类固定为 3，且每种水的数据范围只有 100100100，可直接使用递归进行求解。
为了尽可能的凑成多的对数，我们可以每次取剩余数量最多且不为 0 的两类水进行成组（因此每次处理前需要先对当前 amount 进行排序），直到没有水剩余，或只有一类水的剩余数据量不为 0（剩下的水只能独自生成）。
代码：
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);
}
}
- 时间复杂度：由于
amount的长度固定为3，因此排序消耗可视为常量；每次至少会消耗两杯水，直到递归结束或只剩下一种水。复杂度为 O(∑i=02amount[i])O(\sum_{i = 0}^{2} amount[i])O(∑i=02amount[i]) - 空间复杂度：忽略递归和排序带来的额外空间开销，复杂度为 O(1)O(1)O(1)
贪心 + 数学
我们已经知道可以通过「每次取剩余数量最多且不为 0 的水成对」来实现最少生成次数。
那么是否存在直接计算最少生成次数的方法，而不是采用逐回合模拟。
考虑对 amount 进行排序，分别使用 a、b 和 c 代表剩余次数递增的三种种类。
根据 a+ba + ba+b 和 ccc 的大小关系进行分情况讨论：
-
a+b≤ca + b \leq ca+b≤c，此时每消耗一个 ccc 都可以顺带消除一个 aaa 或 bbb，因此最少生成次数为 ccc；
-
a+b>ca + b > ca+b>c，此时考虑其之间的差值 t=a+b−ct = a + b - ct=a+b−c，若能顺利通过 t2\frac{t}{2}2t 次对 aaa 和 bbb 的合并，可以将局面转成情况一，最少生成次数为 t2+c\frac{t}{2} + c2t+c；
考虑起始是否能先对 aaa 和 bbb 进行 t2\frac{t}{2}2t 个回合，由于我们有 a≤ba \leq ba≤b，我们只需考虑是否必然有 a≥t2a \geq \frac{t}{2}a≥2t 即可，可通过反证法证明 a<t2a < \frac{t}{2}a<2t 必然不成立，若有 a<t2a < \frac{t}{2}a<2t，则有 2a<a+b−c2a < a + b - c2a<a+b−c => a<b−ca < b - ca<b−c，由于 b≤cb \leq cb≤c，则有 a<0a < 0a<0，与原条件冲突。
最后，为了处理 ttt 的奇偶性问题，先用 aaa 和 bbb 进行 ⌈a+b−c2⌉\left \lceil \frac{a + b - c}{2} \right \rceil⌈2a+b−c⌉ 抵消操作，再与 ccc 进行抵消
代码：
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;
}
}
- 时间复杂度：O(1)O(1)O(1)
- 空间复杂度：O(1)O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2335 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉