题目大意：
制作 m 束花所需的最少天数
给你一个整数数组 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 == n
- 1 <= n <= 10^5
- 1 <= bloomDay[i] <= 10^9
- 1 <= m <= 10^6
- 1 <= k <= n
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1482
解题思路分析：
对于第D天时，能制作的花束个数，取决于所有值都要大于等于D（已开花）并且长度为k的不重合子数组个数。另外我们可以得知，随着D的增大，能制作的花束个数会增加，反之会减少。这是一个线性关系，因此，解题时会很容易想到使用二分查找的思路。
- 首先使用m乘以k判断制作m个花束一共需要多少多花，如果该数量大于花园总花朵数，返回-1。
- 循环一遍数组，找到最先开花（low）的时间与最晚开花的时间（high）
- 利用low和high作为二分查找的两个边界。（以下为标准二分思路）取中间值mid，并查看第mid天可以制作花束的数量。循环一遍数组，查看数值大于等于mid的连续子区间长度，该长度与k求商可得该子区间可制作花束的个数，并向后继续寻找连续大于等于mid的子区间。直到循环完数组中所有元素，可得当前一共可制作花束的个数。如果该个数大于等于m，将high变为mid-1。反之将low变为mid加一。重复上述过程直到low大于high为止
- low为最终答案。
实现代码：
public int minDays(int[] bloomDay, int m, int k) {
// 花园中所有的花数量不够制作m个花束，返回-1
if(m*k>bloomDay.length) return -1;
// 花园中开花时间的最大值与最小值
int low=bloomDay[0],high=bloomDay[0];
for(int b : bloomDay){
low=Math.min(low,b);
high=Math.max(high,b);
}
// 二分查找
while(low<=high){
// 当前为第mid天时
int mid=(low+high)/2;
int count=0;
int length=0;
// 计算当前能制作的花束个数
for(int b : bloomDay){
if(b<=mid){
length++;
}else{
count+=length/k;
length=0;
}
}
count+=length/k;
// 如果个数大于等于需求m，减小high值
if(count>=m) high=mid-1;
else low=mid+1; // 反之增加low值
}
return low;
} 本题解法执行时间为16ms。
Runtime: 16 ms, faster than 94.31% of Java online submissions for Minimum Number of Days to Make m Bouquets.
Memory Usage: 48.1 MB, less than 100.00% of Java online submissions for Minimum Number of Days to Make m Bouquets.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1482-minimum-number-of-days-to-make-m-bouquets-解题思路分析/