算法 - 递归 & 数学分析 - 2335. 装满杯子需要的最短总时长 详细解析

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

说明

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

题解思路

• 按题意看，装满所有杯子需要的最少时间一定需要尽可能多的一次倒2杯水
• 那么就可以转化为：尽量每次倒两种水，需要的时间

简单模拟 + 递归

• 尽量每次倒两种水，需要的时间
• 那么每次倒所需最多的次多的两种，最后如果有余那么加上这个时间
• 按照题意模拟：
  • 每次先对数组进行排序
  • 如果仅有一种水的需求了，那么就返回这个需求的数量
  • 否则将最多的和次多的各减一
  • 操作数加一进行递归
• 数组长度固定为 3 ，所以排序的时间复杂度为 O(1)
• 最终时间复杂度仅取决于amount[n]的大小，为 O(n)
• 空间复杂度为 O(1)

数学分析

• 细看题目，实际上这个问题可以通过数学的方式来求解
• 设定需求最多的水数量为 c ， 次多的水数量为 b ，最少的水数量为 a
  • 如果 c >= a + b ，那么每次倒c水的时候，都能带走一杯 a 或者 b ，最终加上 c 的剩余即为最优的用时
    • 那就是每次都倒 c 的水，有 a 有 b 的时候带上倒，没了就只倒 c ，最终的用时就是倒完 c 的时间
    • 最优的耗时就是 c的值
  • 如果 c < a + b
    • 这个情况的最优策略就取决于 a + b 与 c 的差值 t ，t = a + b - c
      • 因为如果将在 t/2 的时间内，将 a 与 b 合起来倒掉 t 杯水，那么问题就转化成了上面的c >= a + b，最优时间为 c
    • 现在就需要证明在 t/2 的时间内，能不能将 a 与 b 合起来倒掉 t 杯水，这取决于 a 是否大于等于 t/2
    • 反证法：
      • 假设 a < t/2
      • => t < t/2 + b - c
      • => t/2 < b - c
      • 因为 b < c ，且t一定大于0，假设显然不成立
      • 那么就能证明 a 一定大于等于 t/2
    • 需要的时间就是先用 t/2 的时间将问题转化为 c >= a + b 的情况
    • 最终耗时：t/2 + c => (a + b - c)/2 + c
    • 实现需要考虑奇偶，所以为(a + b - c + 1)/2 + c
• 时间复杂度为 O(1)
• 空间复杂度为 O(1)

Code

简单模拟 + 递归

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

数学分析

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;
        return (a + b - c + 1) / 2 + c;
    }
}
1
2
3
4
5
6
7
8