LeetCode 题解工作台
全部开花的最早一天
你有 n 枚花的种子。每枚种子必须先种下，才能开始生长、开花。播种需要时间，种子的生长也是如此。给你两个下标从 0 开始的整数数组 plantTime 和 growTime ，每个数组的长度都是 n ： plantTime[i] 是 播种 第 i 枚种子所需的 完整天数 。每天，你只能为播种某一枚种…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
根据题目描述，我们知道，每一天只能为一枚种子进行播种，因此不管什么播种顺序，所有种子的播种时间之和总是等于 $\sum_{i=0}^{n-1} plantTime[i]$。那么，为了让尽快让所有种子开花，我们应该尽快播种生长时间最长的种子。因此，我们可以对所有种子按照生长时间从大到小进行排序，然后依次进行播种。 时间复杂度 $O(n \times \log n)$，空间复杂度 。其中 是种子的数…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
你有 n 枚花的种子。每枚种子必须先种下，才能开始生长、开花。播种需要时间，种子的生长也是如此。给你两个下标从 0 开始的整数数组 plantTime 和 growTime ，每个数组的长度都是 n ：
plantTime[i]是 播种 第i枚种子所需的 完整天数 。每天，你只能为播种某一枚种子而劳作。无须 连续几天都在种同一枚种子，但是种子播种必须在你工作的天数达到plantTime[i]之后才算完成。growTime[i]是第i枚种子完全种下后生长所需的 完整天数 。在它生长的最后一天 之后 ，将会开花并且永远 绽放 。
从第 0 开始，你可以按 任意 顺序播种种子。
返回所有种子都开花的 最早 一天是第几天。
示例 1：
输入：plantTime = [1,4,3], growTime = [2,3,1] 输出：9 解释：灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。 一种最优方案是： 第 0 天，播种第 0 枚种子，种子生长 2 整天。并在第 3 天开花。 第 1、2、3、4 天，播种第 1 枚种子。种子生长 3 整天，并在第 8 天开花。 第 5、6、7 天，播种第 2 枚种子。种子生长 1 整天，并在第 9 天开花。 因此，在第 9 天，所有种子都开花。
示例 2：
输入：plantTime = [1,2,3,2], growTime = [2,1,2,1] 输出：9 解释：灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。 一种最优方案是： 第 1 天，播种第 0 枚种子，种子生长 2 整天。并在第 4 天开花。 第 0、3 天，播种第 1 枚种子。种子生长 1 整天，并在第 5 天开花。 第 2、4、5 天，播种第 2 枚种子。种子生长 2 整天，并在第 8 天开花。 第 6、7 天，播种第 3 枚种子。种子生长 1 整天，并在第 9 天开花。 因此，在第 9 天，所有种子都开花。
示例 3：
输入：plantTime = [1], growTime = [1] 输出：2 解释：第 0 天，播种第 0 枚种子。种子需要生长 1 整天，然后在第 2 天开花。 因此，在第 2 天，所有种子都开花。
提示：
n == plantTime.length == growTime.length1 <= n <= 1051 <= plantTime[i], growTime[i] <= 104
解题思路
方法一：贪心 + 排序
根据题目描述，我们知道，每一天只能为一枚种子进行播种，因此不管什么播种顺序，所有种子的播种时间之和总是等于 。那么，为了让尽快让所有种子开花，我们应该尽快播种生长时间最长的种子。因此，我们可以对所有种子按照生长时间从大到小进行排序，然后依次进行播种。
时间复杂度 ，空间复杂度 。其中 是种子的数量。
class Solution:
def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
ans = t = 0
for pt, gt in sorted(zip(plantTime, growTime), key=lambda x: -x[1]):
t += pt
ans = max(ans, t + gt)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate shows understanding of greedy strategies and can apply sorting based on custom criteria.
- question_mark
Candidate demonstrates the ability to simulate the plant-grow-bloom sequence and compute the final result efficiently.
- question_mark
Candidate struggles with determining the right plant order and the impact of plantTime and growTime on bloom day.
常见陷阱
外企场景- error
Not sorting the seeds correctly by growTime, which results in a suboptimal planting order and delays bloom times.
- error
Misunderstanding the relationship between plantTime, growTime, and the overall timeline, leading to incorrect calculations.
- error
Failing to handle edge cases, such as when all seeds have the same plantTime or growTime, which may require careful handling in the sorting step.
进阶变体
外企场景- arrow_right_alt
What if there are different constraints on the maximum values for plantTime and growTime?
- arrow_right_alt
How does this problem change when considering additional constraints, like limited planting space or simultaneous blooming?
- arrow_right_alt
Can the solution be optimized further for cases where n is very large (e.g., n > 10^5)?