全部开花的最早一天
难度:
标签:
题目描述
You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed takes time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each:
plantTime[i]is the number of full days it takes you to plant theithseed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have workedplantTime[i]days on planting it in total.growTime[i]is the number of full days it takes theithseed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever.
From the beginning of day 0, you can plant the seeds in any order.
Return the earliest possible day where all seeds are blooming.
Example 1:
Input: plantTime = [1,4,3], growTime = [2,3,1] Output: 9 Explanation: The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms. One optimal way is: On day 0, plant the 0th seed. The seed grows for 2 full days and blooms on day 3. On days 1, 2, 3, and 4, plant the 1st seed. The seed grows for 3 full days and blooms on day 8. On days 5, 6, and 7, plant the 2nd seed. The seed grows for 1 full day and blooms on day 9. Thus, on day 9, all the seeds are blooming.
Example 2:
Input: plantTime = [1,2,3,2], growTime = [2,1,2,1] Output: 9 Explanation: The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms. One optimal way is: On day 1, plant the 0th seed. The seed grows for 2 full days and blooms on day 4. On days 0 and 3, plant the 1st seed. The seed grows for 1 full day and blooms on day 5. On days 2, 4, and 5, plant the 2nd seed. The seed grows for 2 full days and blooms on day 8. On days 6 and 7, plant the 3rd seed. The seed grows for 1 full day and blooms on day 9. Thus, on day 9, all the seeds are blooming.
Example 3:
Input: plantTime = [1], growTime = [1] Output: 2 Explanation: On day 0, plant the 0th seed. The seed grows for 1 full day and blooms on day 2. Thus, on day 2, all the seeds are blooming.
Constraints:
n == plantTime.length == growTime.length1 <= n <= 1051 <= plantTime[i], growTime[i] <= 104
代码结果
运行时间: 189 ms, 内存: 31.2 MB
// Java Stream solution for the given problem
// Idea: Use streams to sort the seeds based on their growTime in descending order and calculate the earliest full bloom day.
import java.util.*;
import java.util.stream.*;
public class Solution {
public int earliestFullBloom(int[] plantTime, int[] growTime) {
int n = plantTime.length;
List<int[]> seeds = IntStream.range(0, n)
.mapToObj(i -> new int[]{plantTime[i], growTime[i]})
.sorted((a, b) -> Integer.compare(b[1], a[1]))
.collect(Collectors.toList());
int currentDay = 0;
int maxBloomDay = 0;
for (int[] seed : seeds) {
currentDay += seed[0]; // Plant the seed
maxBloomDay = Math.max(maxBloomDay, currentDay + seed[1]); // Calculate bloom day
}
return maxBloomDay;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] plantTime = {1, 4, 3};
int[] growTime = {2, 3, 1};
System.out.println(sol.earliestFullBloom(plantTime, growTime)); // Output: 9
}
}
解释
方法:
此题的关键是确定种子的播种顺序，以使得所有种子尽可能早地开花。考虑到种子的生长时间对总开花时间的影响较大，特别是对于生长时间长的种子，如果将它们放在后面播种，它们的开花时间将极大地延后。因此，一个有效的策略是优先播种生长时间长的种子。具体步骤如下：\n1. 将所有种子按照生长时间从大到小排序。\n2. 按排序后的顺序依次播种每一枚种子，并计算每枚种子的开花时间。\n3. 开花时间是播种完成后紧接着的生长时间，总的开花时间为所有种子中最晚的一个开花时间。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在计算最终所有种子开花的最早一天时，为什么使用`max(res, serial + io)`来更新结果？
▷🦆
代码中的变量`serial`和`res`分别代表什么含义，它们如何共同作用于结果计算？
▷