【面试高频题】难度 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 = 3$
$0 <= amount[i] <= 100$

排序 + 递归

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

为了尽可能的凑成多的对数，我们可以每次取剩余数量最多且不为 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(\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$ 进行抵消

代码：

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;
    }

}