LeetCode 1482中等二分答案
制作 m 束花所需的最少天数 图解题解
这道题到底在问什么
花园里第 i 朵花在 bloomDay[i] 天开放。要做 m 束花，每束需要相邻的 k 朵已开的花。问最少等多少天能做出 m 束？做不出返回 −1。
- bloomDay
- [1,10,3,10,2]
- m, k
- m=3, k=1
- 输出
- 3
最优解：一步一步想明白
- 3想象一个开关：天数小的时候做不出 m 束(false)，天数大到某个点开始一直能做(true)。一条 false…falsetrue…true 的线——我们要找的就是第一个 true 的位置。单调 = 可二分。
- 4二分范围 = 最小开放日到最大开放日(再早没花开、再晚没意义)。判定函数 canMake(d)：从左到右扫，遇到已开的花就接到当前连续段上，每攒够 k 朵立刻摘成一束、计数清零；遇到没开的花连续段就断掉。够 m 束就 true。
- 5先看小天数够不够 · 已开/未开拿小天数 d=2 试水。开放日 ≤ 2 的花算开了：下标 0(日1)、2? 不，下标 2 是日 3 > 2 还没开。下标 1、3(日10)和下标 2(日3)都没开，只有下标 0、4 开了。下面一朵一朵扫、攒连续段。
- 6run=1，攒够 k=1 → 摘 1 束指针到第 0 朵，日 1 ≤ 2 已开，连续段长 run=1。k=1，攒够了！立刻摘成 1 束，run 清零重新攒。已有 1 束。
- 7run 断掉 → 清零指针到第 1 朵，日 10 > 2 没开。一旦碰到没开的花，当前连续段就断了，run 归零——花束必须是相邻的 k 朵，中间隔着没开的花不能拼。
- 8仍未开 · run=0指针到第 2 朵，日 3 > 2 也没开，run 保持 0。这朵花要等到第 3 天才开，现在还轮不到它。
- 9仍未开 · run=0指针到第 3 朵，日 10 还是没开，run 仍是 0。前面 4 朵只摘出了 1 束。
- 10run=1 → 再摘 1 束指针到最后一朵，日 2 ≤ 2 已开，run=1 攒够 k，再摘 1 束。扫完了，一共 2 束。
- 11canMake(2) = falsed=2 只做出 2 束 < 3，不够。说明真正的答案在 2 的右边——这就是二分要往右收的依据。下面正式开二分。
- 12lo=1, hi=10现在把舞台当成天数刻度尺：最早第 1 天有花开、最晚第 10 天全开，答案就夹在 [1,10] 之间。lo、hi 两根指针往中间夹，找第一个能做出 m 束的天数。
- 13mid = (1+10)/2 = 5取中间天数 mid=5。问：等到第 5 天，能不能做出 3 束？用刚才那套贪心扫一遍。
- 14日 ≤ 5 的花算开第 5 天：开放日 ≤ 5 的花开了——下标 0、2、4(日 1、3、2)。k=1 每朵单独成束，三朵分别成段，3 束 ≥ 3，做得出！
- 15canMake(5)=true → 收右界d=5 够了！那答案一定 ≤ 5，hi 收到 5。注意是 hi=mid 不是 mid−1——因为第 5 天本身可能就是最优解，得留着。范围缩成天数 [1,5]。
- 16mid = (1+5)/2 = 3在新范围 [1,5] 里取中间天数 mid=3。再问：第 3 天够不够 3 束？
- 17日 ≤ 3 的花算开第 3 天：下标 2 的花(日 3)正好开了，加上下标 0、4，还是 3 朵开。k=1 → 3 束 ≥ 3，依然够！
- 18canMake(3)=true → 收右界第 3 天也够，hi 收到 3。答案继续往左压，范围只剩 [1,3]。我们还在找「第一个够的天数」，所以哪怕够了也要试更小的。
- 19mid = (1+3)/2 = 2范围 [1,3] 取中点 mid=2。第 2 天够不够？这个我们开头已经扫过——只做出 2 束。
- 20canMake(2)=false → 推左界第 2 天只做出 2 束，不够。说明答案严格大于 2，lo 推到 3。现在 lo 和 hi 都指向天数 3，要撞上了。
- 21lo==hi，停！答案=3 天lo 撞上 hi，二分停下。答案就是 3 天——比 3 小做不出 3 束，第 3 天恰好够，正是那条单调线上第一个 true 的位置。
- 22bloomDay=[7,7,7,7,12,7,7], k=3k=1 时每朵单独成束，看不出「连续」的关键。换个例子 bloomDay=[7,7,7,7,12,7,7]，k=3：现在每束要挨着的 3 朵。下标 4 的花要等到第 12 天，它把数组劈成了两段。
- 23下标4没开 → 断成两段第 7 天，下标 4(日12)还没开把队伍劈成两段。左段 4 朵连着，每 3 朵一束 → 摘 1 束(剩 1 朵不够)；右段只 2 朵 → 0 束。共 1 束。要 m=2 束就不够。
- 24缺口补上 → 连成一整段等到第 12 天，下标 4 的花也开了，7 朵连成一整段，每 3 朵一束 → 摘 2 束(剩 1 朵)，够 m=2！这例子答案 12。看清了吗——缺口决定能凑几束，这就是为什么要数「连续段」。
- 28这是「二分答案」的通用套路：不在数组下标上二分，而是在答案本身的取值范围上二分，配一个 O(n) 的 check 函数判可行性。LC410 分割数组、LC875 吃香蕉、LC1011 运货都是同一招——认出单调性是关键。
⚠️ 容易写错的地方
✗ 错：忘了判 m·k > n 的死局
✓ 对：开头 m*k > n 直接 return −1
总共就 n 朵花，要 m 束每束 k 朵，凑不齐就永远做不出
✗ 错：够时写 lo=mid+1
✓ 对：够 → hi=mid；不够 → lo=mid+1
找「第一个 true」，mid 够时它本身可能是答案，不能跳过
✗ 错：m*k 用 int 相乘
✓ 对：用 long 防溢出
m、k 都可到 1e9 级，int 相乘会溢出，判定死局就错了
完整代码（Python / C++ / Java）
Python
class Solution:
def minDays(self, bloomDay, m, k):
if m * k > len(bloomDay): return -1 # 花不够，永远做不出
def canMake(day): # d 天能做出 ≥ m 束？
bouquets = run = 0
for b in bloomDay:
if b <= day: # 这朵开了，接上连续段
run += 1
if run == k: # 攒够 k 朵，摘一束
bouquets += 1; run = 0
else: # 没开，连续段断掉
run = 0
return bouquets >= m
lo, hi = min(bloomDay), max(bloomDay)
while lo < hi: # 二分第一个 true 的天数
mid = (lo + hi) // 2
if canMake(mid): hi = mid # 够 → 答案 ≤ mid
else: lo = mid + 1 # 不够 → 答案 > mid
return loC++
class Solution {
public:
int minDays(vector<int>& bloomDay, int m, int k) {
long need = (long)m * k;
if (need > (long)bloomDay.size()) return -1;
int lo = *min_element(bloomDay.begin(), bloomDay.end());
int hi = *max_element(bloomDay.begin(), bloomDay.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int bouquets = 0, run = 0;
for (int b : bloomDay) {
if (b <= mid) { if (++run == k) { bouquets++; run = 0; } }
else run = 0;
}
if (bouquets >= m) hi = mid; // 够
else lo = mid + 1; // 不够
}
return lo;
}
};Java
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
long need = (long) m * k;
if (need > bloomDay.length) return -1;
int lo = Integer.MAX_VALUE, hi = 0;
for (int b : bloomDay) { lo = Math.min(lo, b); hi = Math.max(hi, b); }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int bouquets = 0, run = 0;
for (int b : bloomDay) {
if (b <= mid) { if (++run == k) { bouquets++; run = 0; } }
else run = 0;
}
if (bouquets >= m) hi = mid; // 够
else lo = mid + 1; // 不够
}
return lo;
}
}复杂度
时间复杂度
O(n · log(maxDay))
二分天数 O(log(maxDay−minDay))，每次判定扫整个数组 O(n)
空间复杂度
O(1)
只用 lo/hi/mid 和 run/bouquets 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 制作 m 束花所需的最少天数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么能二分天数？+
天数越大开的花越多，能做的花束数单调不减，「d 天够不够 m 束」是一条 false…true 的单调线，故可二分找第一个 true。
判定函数 canMake 怎么写？+
扫一遍 bloomDay，开放日 ≤ d 的花接到当前连续段 run 上，run 满 k 就摘一束清零；遇没开的花 run 清零。最后 bouquets ≥ m 即可行。
复杂度与边界？+
O(n·log maxDay)；空间 O(1)。注意 m·k>n 返回 −1，且 m·k 要用 long 防溢出。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 制作 m 束花所需的最少天数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。