原文链接: https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets
英文原文
Given an integer array bloomDay, an integer m and an integer k.
We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1 Output: 3 Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden. We need 3 bouquets each should contain 1 flower. After day 1: [x, _, _, _, _] // we can only make one bouquet. After day 2: [x, _, _, _, x] // we can only make two bouquets. After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2 Output: -1 Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.
Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3 Output: 12 Explanation: We need 2 bouquets each should have 3 flowers. Here's the garden after the 7 and 12 days: After day 7: [x, x, x, x, _, x, x] We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent. After day 12: [x, x, x, x, x, x, x] It is obvious that we can make two bouquets in different ways.
Example 4:
Input: bloomDay = [1000000000,1000000000], m = 1, k = 1 Output: 1000000000 Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.
Example 5:
Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2 Output: 9
Constraints:
bloomDay.length == n1 <= n <= 10^51 <= bloomDay[i] <= 10^91 <= m <= 10^61 <= k <= n
中文题目
给你一个整数数组 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
通过代码
高赞题解
二分查找
题目需要求得「所需的最少天数」。
假设「所需的最少天数」为 ans ，那么以 ans 为分割点的数轴具有「二段性」：
- 天数范围落在 $[0, ans)$ 无法制作完成
- 天数范围在 $[ans, +∞)$ 可以制作完成
因此可以通过「二分」来找到分割点 ans。
接下来我们需要确定「二分范围」，一个及格的「二分范围」只需要确保答案落在范围即可。
显然范围的左边界为 $0$（代表尚未有花绽放），范围的右边界为 $max(bloomDay[i])$（最后一朵花的开放时间，代表所有花都开完）。
我们既可以通过遍历 $bloomDay[]$ 数组来取得「精确右边界」，也可以直接根据数据范围 1 <= bloomDay[i] <= 10^9 来确定「粗略右边界」。
由于二分查找本身具有“折半”效率，因此两者不会有太大效率差距，我这里采用「粗略右边界」的方式。
代码：
[]class Solution { int n, m, k; boolean[] fl; public int minDays(int[] nums, int _m, int _k) { n = nums.length; m = _m; k = _k; if (n < m * k) return -1; fl = new boolean[n]; int l = 0, r = (int)1e9; while (l < r) { int mid = l + r >> 1; if (check(nums, mid)) { r = mid; } else { l = mid + 1; } } return check(nums, r) ? r : -1; } boolean check(int[] nums, int mid) { for (int i = 0; i < n; i++) { fl[i] = nums[i] <= mid; } int cnt = 0; for (int i = 0; i < n && cnt < m; ) { if (fl[i]) { int cur = 1, j = i; while (cur < k && j + 1 < n && fl[j + 1]) { j++; cur++; } if (cur == k) cnt++; i = j + 1; } else { i++; } } return cnt >= m; } }
- 时间复杂度：
check函数的复杂度为 $O(n)$。整体复杂度为 $O(n\log{1e9})$ - 空间复杂度：$O(n)$
优化 check 函数
不难发现，上述 check 函数每次都先将所有已开的花预处理出来。复杂度是严格 $O(n)$。
其实这个过程也能下放到统计逻辑去做，这样能够让 check 函数的复杂度从严格 $O(n)$ 变为最坏情况 $O(n)$，同时省去 $fl[]$ 数组，将空间优化至 $O(1)$。
代码（感谢 @Benhao 同学提供的其他语言版本）：
[]class Solution { int n, m, k; public int minDays(int[] nums, int _m, int _k) { n = nums.length; m = _m; k = _k; if (n < m * k) return -1; int l = 0, r = (int)1e9; while (l < r) { int mid = l + r >> 1; if (check(nums, mid)) { r = mid; } else { l = mid + 1; } } return check(nums, r) ? r : -1; } boolean check(int[] nums, int mid) { int cnt = 0; for (int i = 0; i < n && cnt < m; ) { int cur = nums[i] <= mid ? 1 : 0, j = i; if (cur > 0) { while (cur < k && j + 1 < n && nums[j + 1] <= mid) { j++; cur++; } if (cur == k) cnt++; i = j + 1; } else { i++; } } return cnt >= m; } }
[]class Solution: def minDays(self, bloomDay: List[int], m: int, k: int) -> int: def check(mid): i = cnt = 0 while i < n and cnt < m: cur = 1 if bloomDay[i] <= mid else 0 j = i if cur > 0: while cur < k and j + 1 < n and bloomDay[j+1] <= mid: j += 1 cur += 1 if cur == k: cnt += 1 i = j + 1 else: i += 1 return cnt >= m n = len(bloomDay) if n < m * k: return -1 l, r = m * k, max(bloomDay) while l < r: mid = l + r >> 1 if check(mid): r = mid else: l = mid + 1 return r
- 时间复杂度：
check函数的复杂度为 $O(n)$。整体复杂度为 $O(n\log{1e9})$ - 空间复杂度：$O(1)$
其他「二分」相关题解
二分模板
29. 两数相除 : 二分 + 倍增乘法解法（含模板）二分本质 & 恢复二段性处理
33. 搜索旋转排序数组（找目标值） : 严格 O(logN)，一起看清二分的本质
81. 搜索旋转排序数组 II（找目标值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质
二分 check 函数如何确定
34. 在排序数组中查找元素的第一个和最后一个位置 : 考察对「二分」的理解，以及 check 函数的「大于 小于」怎么写二分答案的题目
1482. 制作 m 束花所需的最少天数 : 利用「二段性」找分割点，以及优化 check 函数
1011. 在 D 天内送达包裹的能力 : 利用「二段性」找分割点，以及如何确定「二分范围」
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 31737 | 54081 | 58.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
