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

2026-03-23 HGNULB 约 12 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

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

题意分析

给一排花，bloomDay[i] 表示第 $i$ 朵花在第几天开放。要制作 $m$ 束花，每束需要 $k$ 朵位置相邻且已经开放的花，每朵花只能用于一束。问最少等到第几天能做出这 $m$ 束，做不出返回 $-1$。

先看无解条件：$m$ 束各吃 $k$ 朵，总共需要 $m \times k$ 朵花，若 $m \times k$ 超过数组长度就永远不可能，直接返回 $-1$。注意 $m$ 与 $k$ 都可达 $10^5$ 级别，$m \times k$ 会溢出 int，判断时要么升 long，要么改写成 $m > n / k$ 这种不做乘法的形式。

「相邻」这个词把问题锁死在原数组的顺序上：不能排序，不能挑任意 $k$ 朵，只能在下标连续的段里取。这意味着任何「按开花时间排序后贪心取前若干朵」的思路都是错的。

真正的算法信号藏在单调性里：天数越大，已开放的花只增不减，能凑出的花束数也只增不减。答案空间是天数，而「第 $d$ 天能否做出 $m$ 束」是关于 $d$ 的单调布尔函数——一旦某天可行，之后每天都可行。数据范围 $n \le 10^5$、$bloomDay[i] \le 10^9$ 也印证了这一点：答案值域巨大而数组不长，适合在值域上做对数级搜索、每次用 $O(n)$ 验证。

边界要盯住三处：$k = 1$ 时每朵花自成一束，退化为「第 $m$ 小的开花日」；答案一定是某个 bloomDay[i] 的取值，所以搜索区间可以收紧到 $[\min, \max]$ 而不必从 $1$ 到 $10^9$；以及 $m \times k$ 恰好等于 $n$ 的情形，此时必须整排花全开且严丝合缝地切成 $m$ 段。

解法：二分最少可行天数

核心思路

暴力做法是从第 $1$ 天开始逐天检查能否做出 $m$ 束，直到成功。检查一次是 $O(n)$，而天数上限是 $10^9$，总代价 $O(10^9 n)$，完全不可行。瓶颈在于「逐天试探」浪费了单调性——既然可行性是一个从 false 突变到 true 且再不回头的阶跃函数，就没必要一格一格挪。

关键观察正是这个单调性，它值得说清楚为什么成立：把「第 $d$ 天」理解为一个 01 掩码，bloomDay[i] <= d 的位置为 $1$。$d$ 增大时，掩码上的 $1$ 只会增加不会减少，于是每一段连续 $1$ 的长度只增不减、且不同段可能合并成更长的段。而一段长度为 $L$ 的连续开花能产出 $\lfloor L/k \rfloor$ 束，$L$ 变大或段合并都不会让总束数下降。所以 canMake(d) 一旦为真，对所有 $d' > d$ 恒真。

于是把「求最小天数」转成「在有序的可行性序列上找第一个 true 的位置」，也就是二分答案。搜索区间取 $[\min(bloomDay), \max(bloomDay)]$：答案不可能小于最小开花日（那天一朵花都没开，$k \ge 1$ 必然失败），也不可能大于最大开花日（那天全开，若还不行就是无解，而无解已被 $m \times k > n$ 提前拦掉）。

二分的不变量必须写死：循环中始终保持「答案落在闭区间 $[left, right]$ 内」，且 $right$ 恒为一个已知可行的天数（或初始上界），$left - 1$ 恒为一个已知不可行的天数。每轮取 mid，canMake(mid) 为真就把 right 收到 mid（mid 本身可能就是答案，不能写 mid - 1），为假就把 left 推到 mid + 1（mid 已被排除）。区间收敛到单点时 left == right 即为所求。

判定函数 canMake(day) 的不变量则是：扫描到位置 $i$ 时，consecutive 表示以 $i$ 结尾的、尚未被组装成花束的连续开放花朵数，bouquets 表示已经组装完成的花束数。遇到未开放的花把 consecutive 清零（相邻断了），凑满 $k$ 朵就 bouquets++ 并把 consecutive 归零——归零是因为这 $k$ 朵已被消耗，不能再参与下一束，这正是「每朵花只用一次」的体现。

解题步骤

先判 $m \times k > n$ 返回 $-1$。这一步放在最前面，是因为它与开花时间无关，纯粹是资源总量的算术判定；不先判掉的话，二分会在整个值域上白跑一遍最后返回一个假答案。Java 里用 (long) m * k 强转避免溢出，Go 里用 m > len(bloomDay)/k 同样规避了乘法。

一趟扫描求出 bloomDay 的最小值与最大值作为二分区间。用真实值域而不是 $[1, 10^9]$，能少做几轮迭代，更重要的是保证了「区间内一定存在答案」这个前提，让 while (left < right) 退出时的 left 必定合法，不需要额外校验。

while (left < right) 循环，取 mid = left + (right - left) / 2。用减法形式而不是 (left + right) / 2，是为了避免两个接近 $10^9$ 的数相加溢出 int。循环条件用 < 而非 <=，配合下面的收缩规则，退出时区间恰好收成一点。

canMake(mid) 为真时 right = mid。不能写 right = mid - 1：mid 自己是可行的，它有资格当最终答案，砍掉它就丢解了。这一步在维持「right 始终可行」的不变量。

为假时 left = mid + 1。mid 已被证明不可行，它和它左边的所有天数都可以整体丢弃，+1 保证区间严格收缩、循环必然终止。

判定函数里遇到 bloom > day 时清零 consecutive 并 continue。因为花束要求下标连续，一朵没开的花把左右两段彻底隔断，之前攒的零头作废。

判定函数里凑够 $k$ 朵后 bouquets++ 且 consecutive = 0。归零而不是减 $k$，效果相同但更直白地表达了「这 $k$ 朵被拿走了」；同时一旦 bouquets == m 立即返回 true，省掉剩余扫描。

返回 left。退出循环时 left == right，而不变量保证 right 可行、left - 1 不可行，所以 left 正是第一个可行的天数。

以 bloomDay = [1, 10, 3, 10, 2]、m = 3、k = 1 走一遍：

无解判定：$3 \times 1 = 3 \le 5$，继续。区间：left = 1（最小值）、right = 10（最大值）。
第一轮：mid = 1 + (10-1)/2 = 5。canMake(5) 扫描 $[1, 10, 3, 10, 2]$：花 1 开（$1 \le 5$），consecutive = 1 == k，bouquets = 1，归零；花 10 未开，清零；花 3 开，bouquets = 2；花 10 未开；花 2 开，bouquets = 3 == m，返回 true。于是 right = 5，区间 $[1, 5]$。
第二轮：mid = 1 + (5-1)/2 = 3。canMake(3)：花 1 开得 1 束；花 10 未开；花 3 开得 2 束；花 10 未开；花 2 开得 3 束，返回 true。right = 3，区间 $[1, 3]$。
第三轮：mid = 1 + (3-1)/2 = 2。canMake(2)：花 1 开得 1 束；花 10 未开；花 3 未开（$3 > 2$）；花 10 未开；花 2 开得 2 束。扫描结束只有 2 束，返回 false。left = 3，区间 $[3, 3]$。
left == right 退出，返回 $3$。

再看一个 $k > 1$ 的用例 bloomDay = [7, 7, 7, 7, 12, 7, 7]、m = 2、k = 3：$2 \times 3 = 6 \le 7$。第 $7$ 天时开放掩码为 1 1 1 1 0 1 1，前段长 $4$ 产出 $\lfloor 4/3 \rfloor = 1$ 束（用掉前 3 朵，第 4 朵成零头后被第 5 位的未开花清零），后段长 $2$ 不足 $k$，共 $1$ 束，不可行。第 $12$ 天全开，整段长 $7$ 产出 $\lfloor 7/3 \rfloor = 2$ 束，可行。二分最终收敛到 $12$。这个例子说明零头不可跨越断点累积，也说明为什么必须按原顺序扫描而不能只统计总开花数。

代码实现

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long) m * k > bloomDay.length) {
            return -1;
        }

        int left = bloomDay[0];
        int right = bloomDay[0];
        for (int day : bloomDay) {
            left = Math.min(left, day);
            right = Math.max(right, day);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canMake(bloomDay, m, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canMake(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0;
        int consecutive = 0;

        for (int bloom : bloomDay) {
            if (bloom > day) {
                consecutive = 0;
                continue;
            }

            consecutive++;
            if (consecutive == k) {
                bouquets++;
                if (bouquets == m) {
                    return true;
                }
                consecutive = 0;
            }
        }

        return false;
    }
}

func minDays(bloomDay []int, m int, k int) int {
    if m > len(bloomDay)/k {
        return -1
    }

    left, right := bloomDay[0], bloomDay[0]
    for _, day := range bloomDay {
        if day < left {
            left = day
        }
        if day > right {
            right = day
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canMake(bloomDay, m, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

func canMake(bloomDay []int, m int, k int, day int) bool {
    bouquets := 0
    consecutive := 0

    for _, bloom := range bloomDay {
        if bloom > day {
            consecutive = 0
            continue
        }

        consecutive++
        if consecutive == k {
            bouquets++
            if bouquets == m {
                return true
            }
            consecutive = 0
        }
    }

    return false
}

复杂度分析

时间复杂度：$O(n \log D)$，其中 $n$ 是花的数量、$D = \max(bloomDay) - \min(bloomDay)$ 是值域跨度。求最值是一趟 $O(n)$；二分把区间每轮折半，迭代 $O(\log D)$ 次，每次调用 canMake 做一趟 $O(n)$ 线性扫描。本题量级约 $10^5 \times 30 = 3 \times 10^6$，非常宽裕。

空间复杂度：$O(1)$。只用了 left、right、mid 以及判定函数里的 bouquets、consecutive 几个整型变量，没有辅助数组，也没有对输入排序或复制。

关键点总结

看到「最小的最大值 / 最大的最小值 / 最少的天数」且答案值域连续，先问自己「把答案固定住，验证它是否可行是否更容易」。能把最优化问题转成单调的判定问题，就能二分答案。

单调性要能证明，不能只是感觉。本题的证明是「阈值上升 $\Rightarrow$ 开放集合单调扩张 $\Rightarrow$ 每段长度不减、段可能合并 $\Rightarrow$ $\sum \lfloor L_j/k \rfloor$ 不减」，面试时这段推理比代码更值钱。

二分的三要素——循环条件、收缩方式、返回值——必须共享同一套区间语义。本文用的是「$[left, right]$ 含答案且 right 可行」，对应 while (left < right) + right = mid / left = mid + 1 + return left，三者改一个就必须全改。

判定函数里贪心地「一凑满 $k$ 朵就立刻成束」是最优的：花只能相邻取用，段内从左往右紧密切分能榨出 $\lfloor L/k \rfloor$ 束，是该段的上界，留空隙只会更差。这类「局部立即结算」的贪心在区间切分题里很常见。

面试视角：面试官会先看你能否识别出二分答案，再追问三件事——「为什么答案区间可以取 $[\min, \max]$ 而不是 $[1, 10^9]$」（因为答案必是某个开花日），「$m \times k$ 会不会溢出」（会，要么 long 要么改成除法），「canMake 里为什么清零而不是继续累加」（花不能复用，且零头不能跨断点）。这三问答好基本就过了。

易错点总结

可行时写 right = mid - 1：bloomDay = [1, 10, 3, 10, 2]、m = 3、k = 1 时，canMake(3) 为真却把区间压到 $[1, 2]$，最终返回 $2$，正确答案是 $3$。

判定函数凑满一束后忘记清零 consecutive：bloomDay = [1, 1, 1]、m = 3、k = 2 时 consecutive 一路增长，在 $2$ 和 $3$ 处各判一次（若写成 >= k）会误算出多束，把无解或更大的答案错判成第 $1$ 天可行。

未开放的花只是不计数却不清零：bloomDay = [1, 10, 1]、m = 1、k = 2 时会把下标 0 和 2 两朵不相邻的花凑成一束，返回 $1$，正确答案是 $10$。

无解判定写成 m * k > n 且用 int：$m = 10^5$、$k = 10^5$ 时乘积约 $10^{10}$ 溢出成负数，判断不成立，程序继续二分并返回一个不存在的天数，正确应返回 $-1$。

完全漏掉无解判定：bloomDay = [1, 2, 3]、m = 2、k = 3 时二分会一路把 left 推到 right = 3 并返回 $3$，正确答案是 $-1$。

mid 写成 (left + right) / 2：bloomDay 中出现接近 $10^9$ 的值时 left + right 溢出成负数，mid 变负，canMake 判定全假，left 被推到越界值。

循环写成 while (left <= right) 却仍用 right = mid：mid 等于 left 且判定为真时 right 不动，区间不再收缩，死循环。

二分区间下界取 $0$ 或 $1$：虽不影响正确性但会多迭代若干轮；真正危险的是上界取成 $\max$ 之外的估值又漏了无解判定，退出时返回一个没有任何花开的天数。

判定条件写成 bloom >= day 才算开放：bloomDay = [1, 1]、m = 1、k = 2，day = 1 时两朵花都被判成未开，canMake(1) 返回假，最终返回值大于 $1$，正确答案是 $1$。

把 bloomDay 排序后再做判定：bloomDay = [7, 7, 7, 7, 12, 7, 7]、m = 2、k = 3 排序后变成 [7,7,7,7,7,7,12]，第 $7$ 天就能凑出 $2$ 束，返回 $7$，正确答案是 $12$——排序破坏了「相邻」这个前提。

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	二分速度，判定函数是求和向上取整，与顺序无关，比本题少了「相邻」约束
1011. 在 D 天内送达包裹的能力	中等	二分运力，判定是按原序贪心装箱，下界必须取单件最大重量而非 1
410. 分割数组的最大值	困难	二分子数组和上限，判定同为顺序贪心切分，也可用区间 DP 做对照
1552. 两球之间的磁力	中等	二分的是最小间距的最大值，方向相反，需先排序再贪心放球
719. 找出第 K 小的数对距离	困难	判定函数要数「距离不超过 mid 的对数」，内部还需双指针，判定本身是 $O(n)$
1231. 分享巧克力	困难	二分最小块甜度的最大值，判定是顺序累加切段，求的是最大化而非最小化
668. 乘法表中第k小的数	困难	二分值域而非下标，判定靠逐行整除计数，无显式数组可扫
69. x 的平方根	简单	二分答案的最小形态，判定就是一次乘法比较，重点在溢出与边界收敛