Medium

题目描述

给你一个整数数组 bloomDay，以及两个整数 m 和 k。

现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，每朵花 只能 用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1。

示例 1：

输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，_ 表示花还未开。
现在需要制作 3 束花，每束只要 1 朵。
1 天后：[x, _, _, _, _]   // 只能制作 1 束花
2 天后：[x, _, _, _, x]   // 只能制作 2 束花
3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3

示例 2：

输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足所需要求，返回 -1 。

示例 3：

输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵花。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但是不能用后 3 朵盛开的花制作第二束花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。

提示：

  • bloomDay.length == n
  • 1 <= n <= 10⁵
  • 1 <= bloomDay[i] <= 10⁹
  • 1 <= m <= 10⁶
  • 1 <= k <= n

解题思路

这道题的核心思路是二分搜索：

问题分析：

  1. 需要制作 m 束花，每束需要 k 朵相邻的花
  2. 如果在第 x 天能制作出 m 束花，那么第 x+1 天及以后也一定能制作出 m 束花
  3. 这种单调性特征提示我们可以用二分搜索来找最小天数

解题步骤：

  1. 边界判断：如果总花数 n < m * k，直接返回 -1
  2. 二分搜索范围：左边界为数组最小值，右边界为数组最大值
  3. 检查函数：给定天数 day，判断能否制作出至少 m 束花
    • 遍历数组，统计连续开放的花朵数量
    • 当连续花朵数达到 k 时，可以制作一束花
    • 统计总共能制作的花束数

时间复杂度优化：

  • 二分搜索的时间复杂度为 O(log(max-min))
  • 每次检查的时间复杂度为 O(n)
  • 总时间复杂度为 O(n * log(max-min))

这种解法充分利用了问题的单调性，是处理"最小化最大值"或"最大化最小值"问题的经典模式。

代码实现

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        long long total = (long long)m * k;
        if (bloomDay.size() < total) return -1;
        
        int left = *min_element(bloomDay.begin(), bloomDay.end());
        int right = *max_element(bloomDay.begin(), bloomDay.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canMakeBouquets(bloomDay, m, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
private:
    bool canMakeBouquets(const vector<int>& bloomDay, int m, int k, int day) {
        int bouquets = 0;
        int consecutive = 0;
        
        for (int bloom : bloomDay) {
            if (bloom <= day) {
                consecutive++;
                if (consecutive == k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }
        
        return bouquets >= m;
    }
};

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k:
            return -1
        
        left, right = min(bloomDay), max(bloomDay)
        
        def canMakeBouquets(day):
            bouquets = 0
            consecutive = 0
            
            for bloom in bloomDay:
                if bloom <= day:
                    consecutive += 1
                    if consecutive == k:
                        bouquets += 1
                        consecutive = 0
                else:
                    consecutive = 0
            
            return bouquets >= m
        
        while left < right:
            mid = (left + right) // 2
            if canMakeBouquets(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int MinDays(int[] bloomDay, int m, int k) {
        if ((long)bloomDay.Length < (long)m * k) return -1;
        
        int left = bloomDay.Min();
        int right = bloomDay.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CanMakeBouquets(bloomDay, m, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private bool CanMakeBouquets(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0;
        int consecutive = 0;
        
        foreach (int bloom in bloomDay) {
            if (bloom <= day) {
                consecutive++;
                if (consecutive == k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }
        
        return bouquets >= m;
    }
}

var minDays = function(bloomDay, m, k) {
    if (m * k > bloomDay.length) return -1;
    
    const canMakeBouquets = (day) => {
        let bouquets = 0;
        let adjacent = 0;
        
        for (let bloom of bloomDay) {
            if (bloom <= day) {
                adjacent++;
                if (adjacent === k) {
                    bouquets++;
                    adjacent = 0;
                }
            } else {
                adjacent = 0;
            }
        }
        
        return bouquets >= m;
    };
    
    let left = Math.min(...bloomDay);
    let right = Math.max(...bloomDay);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canMakeBouquets(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × log(max - min))，其中 n 是数组长度，max 和 min 分别是数组的最大值和最小值
空间复杂度O(1)，只使用常数额外空间

相关题目