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

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

文章目录

[2335. 装满杯子需要的最短总时长](https://leetcode.cn/problems/minimum-amount-of-time-to-fill-cups/description/)
- 说明
- 题解思路
- - 简单模拟 + 递归
  - 数学分析
- Code
- - 简单模拟 + 递归
  - 数学分析

说明

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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杯水
那么就可以转化为：尽量每次倒两种水，需要的时间

简单模拟 + 递归

尽量每次倒两种水，需要的时间
那么每次倒所需最多的次多的两种，最后如果有余那么加上这个时间
按照题意模拟：
- 每次先对数组进行排序
- 如果仅有一种水的需求了，那么就返回这个需求的数量
- 否则将最多的和次多的各减一
- 操作数加一进行递归
数组长度固定为 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);}
}

数学分析

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