2025年制作 m 束花所需的最少天数（二分法解题套路模板总结）

科技前沿 • 2025-03-24 08:13 • 阅读 27

大家好，我是讯享网，很高兴认识大家。

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中相邻的 k 朵花。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好可以用于一束花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

讯享网

又是二分又是二分！五月份可能是二分月吧哈哈

采用二分法题目的基本规律：已知取值的边界，即最小值和最大值。例如本题中取值边界是 [1, max(bloomDay)] ，最好的情况是第一天，最差的情况是最后一天，这个时候我们就可以用二分查找出最少的天数。

二分法的解题套路：

明确用二分查找之后，即确定框架为：

least, most = 1, max(bloomDay) def fun(days): # 判断是否满足条件的函数 while least<most: mid = (least+most) // 2 if fun(mid): most = mid else: least = mid+1 return least

讯享网

其中我们需要定义一个函数 fun() ，这个函数的目的就是判断是否满足条件，如果满足条件，说明我们选择的答案偏大，需要向左移动：most = mid；如果不满足条件，则说明传入参数偏小，需要向右移动： least = mid+1。

根据题目编写 fun 函数：
本题需要判断在 days 是否可以满足采花，遍历 bloomDay 数组，flowers 表示连续盛开花的朵数，bounch 表示已经制作好的花束个数。

讯享网def canmake(days): flowers = bounch = 0 for i, _ in enumerate(bloomDay): if bloomDay[i] <= days: # 这朵花在days已经盛开 flowers += 1 if flowers == k: # 连续花朵数满足，可以做一束花 bounch += 1 if bounch == m: return True flowers = 0 # 做好一束花，下一束重新计数 else: # 连续花束断开，重新计数 flowers = 0 return bounch == m

最后合成两块代码，完成解题！

class Solution: def minDays(self, bloomDay: List[int], m: int, k: int) -> int: if len(bloomDay) < m*k: return -1 least, most = 1, max(bloomDay) def canmake(days): flowers = bounch = 0 for i, _ in enumerate(bloomDay): if bloomDay[i] <= days: flowers += 1 if flowers == k: bounch += 1 if bounch == m: return True flowers = 0 else: flowers = 0 return bounch == m while least<most: mid = (least+most) // 2 if canmake(mid): most = mid else: least = mid+1 return least

2025年制作 m 束花所需的最少天数（二分法解题套路模板总结）

相关推荐