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

🟢   🔖  贪心 数组 排序 堆（优先队列）  🔗 力扣 LeetCode

题目

You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up 2 cups with different types of water, or 1 cup of any type of water.

You are given a 0-indexed integer array amount of length 3 where amount[0], amount[1], and amount[2] denote the number of cold, warm, and hot water cups you need to fill respectively. Return the minimum number of seconds needed to fill up all the cups.

Example 1:

Input: amount = [1,4,2]

Output: 4

Explanation: One way to fill up the cups is:

Second 1: Fill up a cold cup and a warm cup.

Second 2: Fill up a warm cup and a hot cup.

Second 3: Fill up a warm cup and a hot cup.

Second 4: Fill up a warm cup.

It can be proven that 4 is the minimum number of seconds needed.

Example 2:

Input: amount = [5,4,4]

Output: 7

Explanation: One way to fill up the cups is:

Second 1: Fill up a cold cup, and a hot cup.

Second 2: Fill up a cold cup, and a warm cup.

Second 3: Fill up a cold cup, and a warm cup.

Second 4: Fill up a warm cup, and a hot cup.

Second 5: Fill up a cold cup, and a hot cup.

Second 6: Fill up a cold cup, and a warm cup.

Second 7: Fill up a hot cup.

Example 3:

Input: amount = [5,0,0]

Output: 5

Explanation: Every second, we fill up a cold cup.

Constraints:

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

题目大意

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 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. 关键观察：

   • 如果一个杯子的数量是最大值（max），那么至少需要 max 秒来填满它。
   • 如果两个杯子的总数量加起来超过 max，则需要更多的时间。
   • 每秒最多可以装两个不同的杯子，因此最小秒数是 ceil(sum / 2)，其中 sum 是 3 个杯子的总数量。

2. 两种情况的最大值：

   • 最大值 max：表示至少需要填满最大的那种杯子。
   • 总数的一半 ceil(sum / 2)：表示能够以最快速度装水的时间。
   • 取上述两者中的最大值。

复杂度分析

• 时间复杂度：O(1)，求最大值与求和的时间复杂度是 O(3)，即O(1)。
• 空间复杂度：O(1)，只是用了常数变量。

代码

/**
 * @param {number[]} amount
 * @return {number}
 */
var fillCups = function (amount) {
	const max = Math.max(...amount);
	const sum = amount.reduce((a, b) => a + b, 0);
	return Math.max(max, Math.ceil(sum / 2));
};

相关题目

题号	标题	题解	标签	难度	力扣
1354	多次求和构造目标数组		数组 堆（优先队列）	🔴	🀄️ 🔗
1753	移除石子的最大得分		贪心 数学 堆（优先队列）	🟠	🀄️ 🔗
2141	同时运行 N 台电脑的最长时间		贪心 数组 二分查找 1+	🔴	🀄️ 🔗
2448	使数组相等的最小开销		贪心 数组 二分查找 2+	🔴	🀄️ 🔗