Hard

题目描述

你有 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

示例 3:

输入：plantTime = [1], growTime = [1]
输出：2

约束条件:

  • n == plantTime.length == growTime.length
  • 1 <= n <= 10^5
  • 1 <= plantTime[i], growTime[i] <= 10^4

解题思路

这道题要求我们找到所有花都盛开的最早时间。关键洞察是种植顺序会影响最终结果。

核心思想：

  1. 贪心策略：为了让所有花尽早盛开，我们应该按照生长时间（growTime）从大到小的顺序来安排种植顺序。

  2. 原理分析：

    • 每颗种子的盛开时间 = 种植完成时间 + 生长时间
    • 种植完成时间取决于它前面所有种子的种植时间之和
    • 如果我们先种植生长时间长的种子，它们可以在我们种植后续种子的过程中同时生长

  3. 为什么要按生长时间降序排序？

    • 生长时间长的种子如果放在后面种植，会延迟整体完成时间
    • 先种植生长时间长的种子，可以让它们在种植其他种子时并行生长
    • 这样能最大化并行处理时间，减少总的等待时间

算法步骤：

  1. 将种子按照生长时间降序排序
  2. 顺序种植排序后的种子，累计种植时间
  3. 计算每颗种子的盛开时间，取最大值

推荐解法：贪心 + 排序

代码实现

class Solution {
public:
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
        int n = plantTime.size();
        vector<int> indices(n);
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // 按生长时间降序排序
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            return growTime[a] > growTime[b];
        });
        
        int currentPlantTime = 0;
        int maxBloomTime = 0;
        
        for (int idx : indices) {
            currentPlantTime += plantTime[idx];
            int bloomTime = currentPlantTime + growTime[idx];
            maxBloomTime = max(maxBloomTime, bloomTime);
        }
        
        return maxBloomTime;
    }
};

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        n = len(plantTime)
        
        # 按生长时间降序排序的索引
        indices = sorted(range(n), key=lambda i: growTime[i], reverse=True)
        
        current_plant_time = 0
        max_bloom_time = 0
        
        for idx in indices:
            current_plant_time += plantTime[idx]
            bloom_time = current_plant_time + growTime[idx]
            max_bloom_time = max(max_bloom_time, bloom_time)
        
        return max_bloom_time

public class Solution {
    public int EarliestFullBloom(int[] plantTime, int[] growTime) {
        int n = plantTime.Length;
        var indices = new int[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // 按生长时间降序排序
        Array.Sort(indices, (a, b) => growTime[b].CompareTo(growTime[a]));
        
        int currentPlantTime = 0;
        int maxBloomTime = 0;
        
        foreach (int idx in indices) {
            currentPlantTime += plantTime[idx];
            int bloomTime = currentPlantTime + growTime[idx];
            maxBloomTime = Math.Max(maxBloomTime, bloomTime);
        }
        
        return maxBloomTime;
    }
}

var earliestFullBloom = function(plantTime, growTime) {
    const n = plantTime.length;
    const indices = Array.from({length: n}, (_, i) => i);
    
    // 按生长时间降序排序
    indices.sort((a, b) => growTime[b] - growTime[a]);
    
    let currentPlantTime = 0;
    let maxBloomTime = 0;
    
    for (const idx of indices) {
        currentPlantTime += plantTime[idx];
        const bloomTime = currentPlantTime + growTime[idx];
        maxBloomTime = Math.max(maxBloomTime, bloomTime);
    }
    
    return maxBloomTime;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，主要是排序的时间复杂度
空间复杂度O(n)，需要额外的索引数组存储排序后的顺序

相关题目