题目描述
给定一个整数数组 bloomDay，以及两个整数 m 和 k，要求制作 m 束花，每束花需要 相邻的 k 朵盛开的花。返回制作这些花束所需的最少等待天数，若无法完成则返回 -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
解题思路
1. 问题分析
• 核心条件：每束花需要连续的 k 朵花，且花必须在指定天数盛开。
• 关键矛盾：天数过少无法满足盛开条件，天数过多则可能浪费等待时间。
• 数据范围：数组长度 n 可达 1e5，需高效算法（如 O(n log(max_day))） 。
2. 算法设计 采用 二分查找 + 贪心验证 的组合策略：
1. 二分查找目标天数：
最小可能天数为数组最小值 min(bloomDay)，最大为 max(bloomDay)。通过二分逐步缩小范围
2. 验证函数 check：
对于某个中间天数 mid，遍历数组统计连续盛开的 k 朵花的组数，判断是否满足 m 束
代码实现
/*** 计算制作 m 束花所需的最少天数* @param bloomDay 每朵花的盛开天数数组* @param m 目标花束数量* @param k 每束花需要的连续花朵数* @returns 最少天数，无法完成返回 -1*/
function minDays(bloomDay: number[], m: number, k: number): number {const n = bloomDay.length;if (n < m * k) return -1; // 花朵总数不足// 确定二分范围let low = Math.min(...bloomDay);let high = Math.max(...bloomDay);while (low < high) {const mid = low + Math.floor((high - low) / 2);if (check(bloomDay, mid, m, k)) {high = mid; // 满足条件，尝试更小值} else {low = mid + 1; // 不满足，增加天数}}return low;
}/*** 验证在 days 天内是否能制作 m 束花*/
function check(bloomDay: number[], days: number, m: number, k: number): boolean {let cnt = 0; // 已制作的花束数let flowers = 0; // 当前连续的花朵数for (const day of bloomDay) {if (day <= days) {flowers++;if (flowers === k) {cnt++;flowers = 0; // 重置计数器if (cnt >= m) break; // 提前退出优化}} else {flowers = 0; // 花朵不连续，重置}}return cnt >= m;
}复杂度分析
1. 时间复杂度：
◦ 二分查找：O(log(max_day - min_day))，其中 max_day 和 min_day 是数组极值。
◦ 验证函数 check：单次遍历数组 O(n)。
◦ 总复杂度：O(n log(max_day))，适用于 n ≤ 1e5 的场景。
2. 空间复杂度：
◦ 仅使用常数级额外空间，O(1)
关键点解析
1.二分边界处理：
初始范围设为数组极值，避免无效计算。例如，当 k=1 时，答案可能是任意一朵花的盛开天数
2.连续花朵的统计：
在 check 函数中，遇到未盛开的花需重置计数器，确保每束花由相邻花朵组成
3.提前终止优化：
当已满足 m 束时提前退出循环，减少遍历次数
