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

约 6 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节
标签
数组 二分查找

题目描述

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

image-20260928225945071

image-20260928225945072

题意分析

每束花必须使用原数组中相邻的 k 朵已开放的花，每朵花只能使用一次，求能制作 m 束花的最早日期。若总共不足 m×k 朵花，无论等多久都无法完成。

开花日期范围很大，不能逐天等待；但可以高效判断“到某一天是否已经足够”。一旦某天可行，之后的日期仍可行，因此适合二分第一个可行日期。

解法：二分最少可行天数

核心思路

[!blue]

先固定候选日期 day，把 bloomDay[i] <= day 的位置视为已开放。未开放的位置会截断相邻关系，于是所有可用花分成若干连续段。长度为 L 的一段至多制作 floor(L/k) 束，因为每束都要消耗 k 个不同位置；从左向右每凑满 k 朵就制作一束，恰好能达到这个上限。

判定时用 consecutive 保存当前段中尚未用于成束的连续花数。已开放就加一，凑满 k 就增加 bouquets 并清零；遇到未开放的花也清零，因为之前的零头不能跨过它与后面的花相连。得到 m 束后即可提前返回可行。

日期增加只会增加已开放位置，不会让已经能制作的花束失效，所以可行性必然先假后真。总花数足够时，最大开花日已使所有花连成一整段，必然可行；而最早答案不会小于最小开花日。因此在这两个日期组成的闭区间内二分。

若 mid 可行，答案可能更早，也可能恰好就是 mid，令 right = mid；若不可行，mid 及更早日期全部可以排除，令 left = mid+1。区间始终包含最早可行日期，收缩到一个值时就是答案。

解题步骤

  1. 先检查花数是否足够。Java 使用 (long)m*k，Go 使用 m > n/k，避免需求乘积溢出。
  2. 扫描得到最小、最大开花日，分别作为 left、right。
  3. 在 left < right 时取中点，从原数组左到右统计当天最多能做出的花束数。
  4. 若至少能做 m 束，令 right = mid；否则令 left = mid+1。
  5. 两端重合后返回 left。若所有花同一天开放，初始区间已经只有一个日期，无需进入二分循环。

代码实现

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
}

复杂度分析

设花数为 n，最大与最小开花日之差为 D。

  • 时间复杂度：$O(n\log(D+2))$。初始扫描和每次可行性判定都是 $O(n)$，二分按对数次数缩小日期区间；写成 D+2 也包含 D = 0 时的初始扫描。
  • 空间复杂度：$O(1)$。只维护日期边界、当前连续花数和花束计数。

关键点总结

[!green]

  • 二分依据是日期可行性单调，花在原数组中的相邻顺序必须保持。
  • 每个已开放连续段独立贡献 floor(L/k) 束，凑满立即使用不会少做花束。
  • 成束清零表示花已经使用，遇未开放位置清零表示连续关系中断，两者含义不同。
  • 最大开花日的可行性依赖事先排除了总花数不足的情况。

易错点总结

[!yellow]

  • 排序开花日会改变花园里的相邻关系，使判定结果失真。
  • 只统计开放总数而忽略连续段，可能把互不相邻的花拼成一束。
  • 遇到未开放位置仍保留零头，或成束后不清零，都会破坏 consecutive 的含义。
  • 直接计算 32 位的 m*k 再转为宽类型，溢出已经发生；必须先提升类型，或改用除法比较。
  • 可行时写成 right = mid-1，可能把恰好等于 mid 的最早答案排除。

相似题目

题目 难度 关联与区别
875. 爱吃香蕉的珂珂 中等 同样二分最小可行阈值，本题判定某天能否从已开放的连续花段中取出m组。
1011. 在 D 天内送达包裹的能力 中等 同样固定候选上限后扫描计算可形成的组数，本题未开放位置会打断连续组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/25519739
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！