LeetCode 题解工作台
制作 m 束花所需的最少天数
给你一个整数数组 bloomDay ，以及两个整数 m 和 k 。 现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。 花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开， 恰好 可以用于 一束 花中。 请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
根据题目描述，如果一个天数 可以满足制作 束花，那么对任意 $t' > t$，也一定可以满足制作 束花。因此，我们可以使用二分查找的方法找到最小的满足制作 束花的天数。 我们记花园中最大的开花天数为 ，接下来，我们定义二分查找的左边界 $l = 1$，右边界 $r = mx + 1$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个整数数组 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] 显然，我们可以用不同的方式制作两束花。
示例 4：
输入：bloomDay = [1000000000,1000000000], m = 1, k = 1 输出：1000000000 解释：需要等 1000000000 天才能采到花来制作花束
示例 5：
输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2 输出：9
提示：
bloomDay.length == n1 <= n <= 10^51 <= bloomDay[i] <= 10^91 <= m <= 10^61 <= k <= n
解题思路
方法一：二分查找
根据题目描述，如果一个天数 可以满足制作 束花，那么对任意 ，也一定可以满足制作 束花。因此，我们可以使用二分查找的方法找到最小的满足制作 束花的天数。
我们记花园中最大的开花天数为 ，接下来，我们定义二分查找的左边界 ，右边界 。
然后，我们进行二分查找，对于每一个中间值 ，我们判断是否可以制作 束花。如果可以，我们将右边界 更新为 ，否则，我们将左边界 更新为 。
最终，当 时，结束二分查找。此时如果 ，说明无法制作 束花，返回 ，否则返回 。
因此，问题转换为判断一个天数 是否可以制作 束花。
我们可以使用一个函数 来判断是否可以制作 束花。具体地，我们从左到右遍历花园中的每一朵花，如果当前花开的天数小于等于 ，我们将当前花加入到当前花束中，否则，我们将当前花束清空。当当前花束中的花的数量等于 时，我们将当前花束的数量加一，并清空当前花束。最后，我们判断当前花束的数量是否大于等于 ，如果是，说明可以制作 束花，否则，说明无法制作 束花。
时间复杂度 ，其中 和 分别为花园中的花的数量和最大的开花天数，本题中 。空间复杂度 。
class Solution:
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
def check(days: int) -> int:
cnt = cur = 0
for x in bloomDay:
cur = cur + 1 if x <= days else 0
if cur == k:
cnt += 1
cur = 0
return cnt >= m
mx = max(bloomDay)
l = bisect_left(range(mx + 2), True, key=check)
return -1 if l > mx else l
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N \log D) because binary search reduces the range of days while validating bouquets takes O(N) for each check. Space complexity is O(1) since no additional structures proportional to N are required. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Check if the candidate recognizes the binary search over valid answer space pattern.
- question_mark
Watch if they correctly handle adjacency constraints in the bouquet check.
- question_mark
See if they catch cases where the total flowers are insufficient early.
常见陷阱
外企场景- error
Miscounting adjacent flowers and resetting the counter incorrectly, leading to wrong bouquet counts.
- error
Failing to handle the case where m * k exceeds bloomDay.length and returning an incorrect minimum day.
- error
Iterating sequentially through days instead of using binary search, resulting in TLE for large arrays.
进阶变体
外企场景- arrow_right_alt
Find the maximum number of bouquets possible by a given day instead of the minimum day.
- arrow_right_alt
Change adjacency requirement to allow non-consecutive flowers with a minimum gap between them.
- arrow_right_alt
Determine the earliest day to make bouquets when each bouquet can use variable numbers of adjacent flowers.