当前位置：首页 > news >正文

LeetCode 1482. 制作 m 束花所需的最少天数

news 2025/5/9 9:25:38

题目描述

给定一个整数数组 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;
}