LeetCode-Go 题解1482. Minimum Number of Days to Make m Bouquets二分搜索 贪心校验【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 1482 题「制作 m 束花所需的最少天数」讲解如何用二分搜索 贪心线性校验在单调的解空间[0, maxDay]中快速定位满足条件的最小天数。这是最小化可行解minimize the feasible solution类题目的经典模板先判断可行性单调性再对有序区间二分。读完本文你将掌握这类等待天数 / 分配资源问题从建模、可行性判定到 Go 实现的完整套路并可直接复用本仓库 leetcode/1482.Minimum-Number-of-Days-to-Make-m-Bouquets 中的源码与测试用例进行验证。题目理解给定一个整数数组bloomDay以及两个整数m和k。花园中共有n朵花第i朵花会在第bloomDay[i]天盛开且恰好只能用于一束花。制作一束花需要使用花园中相邻的k朵花。要求返回从花园中摘下m束花所需等待的最少天数如果无法摘到m束花返回-1。关键约束来自题目与 README.md参数约束范围含义bloomDay.length n1 n 10^5花园中花的数量bloomDay[i]1 bloomDay[i] 10^9第 i 朵花的盛开天数m1 m 10^6需要制作的花束数量k1 k n每束花需要的相邻花朵数示例演练示例 1答案落在中间某天Input: bloomDay [1,10,3,10,2], m 3, k 1 Output: 3每束花只需 1 朵花因此开花即可成束。逐天观察x表示已盛开_表示未盛开第 1 天[x, _, _, _, _]只能制作 1 束第 2 天[x, _, _, _, x]只能制作 2 束第 3 天[x, _, x, _, x]可以制作 3 束。答案即第 3 天。示例 2花朵总数不足返回 -1Input: bloomDay [1,10,3,10,2], m 3, k 2 Output: -1需要3 × 2 6朵花但花园只有 5 朵花无论等多久都不可能完成直接返回-1。示例 3强调相邻条件Input: bloomDay [7,7,7,7,12,7,7], m 2, k 3 Output: 12第 7 天[x, x, x, x, _, x, x]前 3 朵相邻可组成 1 束最后 2 朵虽已开但数量不足 3且中间被未开的花隔断不能与前面的花组成一束第 12 天[x, x, x, x, x, x, x]全部盛开可以组成 2 束。答案即第 12 天。示例 4等待最久的天数Input: bloomDay [1000000000,1000000000], m 1, k 1 Output: 1000000000需要等待 10^9 天才能得到一束花说明答案可以取到bloomDay的最大值。示例 5交错花期Input: bloomDay [1,10,2,9,3,8,4,7,5,6], m 4, k 2 Output: 9m × k 8 ≤ n 10可行在解空间内二分第 9 天是第一个能凑齐 4 束花的天数。解题思路为什么可以用二分搜索解空间单调且有序等待天数d越大已盛开的花只会越多或不变可制作的花束数f(d)随d单调不减。因此答案区间一定落在[0, maxDay]maxDay为bloomDay中的最大值并且存在某个阈值ans使得d ans时f(d) md ≥ ans时f(d) ≥ m在这个有序解空间上可以用二分搜索找到第一个满足f(d) ≥ m的下标它即是最少天数。这正是最小化可行解类二分问题的标准特征可行性判定是单调的解空间边界确定。可行性判定check 函数贪心线性扫描对给定的候选天数days从左到右遍历bloomDay若bloomDay[i] days该花未开当前连续段中断flowers清零否则该花已开flowers一旦flowers k立即组成一束bouquets并清零重新计数——因为每朵花恰好只能用一次贪心地在满足相邻条件时立刻成束不会让结果变差遍历结束后若bouquets m说明在days天内可行。整个check是O(n)的线性扫描配合二分后总复杂度为O(n · log maxDay)在n ≤ 10^5、maxDay ≤ 10^9的量级下完全可行。代码实现本仓库的完整实现位于 1482. Minimum Number of Days to Make m Bouquets.go与 README.md 中给出的代码一致如下已补充注释package leetcode import sort func minDays(bloomDay []int, m int, k int) int { // 剪枝需要的花朵总数超过花园容量直接判定不可能 if m*k len(bloomDay) { return -1 } // 求解空间上界所有花都盛开的天数 maxDay : 0 for _, day : range bloomDay { if day maxDay { maxDay day } } // 在 [0, maxDay] 中二分找到第一个满足 bouquets m 的天数 return sort.Search(maxDay, func(days int) bool { flowers, bouquets : 0, 0 for _, d : range bloomDay { if d days { // 未盛开中断连续段 flowers 0 } else { // 已盛开累加连续花朵数凑满 k 朵即成一束 flowers if flowers k { bouquets flowers 0 } } } return bouquets m }) }实现细节说明先剪枝再二分m*k len(bloomDay)时无论等多久都不够花直接返回-1省去无意义的搜索也天然规避了示例 2 这类情形。二分区间[0, maxDay]上界取bloomDay最大值保证存在可行解时答案一定落在区间内sort.Search返回的是满足谓词的第一个索引正好对应最少天数。谓词单调性保证正确性sort.Search要求f(0..i-1) false且f(i..n-1) true而天数越多花束越多恰好满足这一前提。贪心成束的正确性flowers达到k立即成束并清零等价于把每个连续已开区间按长度k切块区间长度为L时可产出的花束数恰为L/k向下取整不会少算也不会多算。测试用例与运行验证本仓库为本题提供了与题目示例一一对应的单元测试位于 1482. Minimum Number of Days to Make m Bouquets_test.gofunc Test_Problem1482(t *testing.T) { qs : []question1482{ {para1482{[]int{1, 10, 3, 10, 2}, 3, 1}, ans1482{3}}, {para1482{[]int{1, 10, 3, 10, 2}, 3, 2}, ans1482{-1}}, {para1482{[]int{7, 7, 7, 7, 12, 7, 7}, 2, 3}, ans1482{12}}, {para1482{[]int{1000000000, 1000000000}, 1, 1}, ans1482{1000000000}}, {para1482{[]int{1, 10, 2, 9, 3, 8, 4, 7, 5, 6}, 4, 2}, ans1482{9}}, } // 逐条断言 minDays(p.bloomDay, p.m, p.k) 与期望答案一致 ... }测试覆盖了五类典型场景答案在中间示例 1、不可能完成返回-1示例 2、相邻性约束示例 3、答案取最大值示例 4以及交替花期的中等规模用例示例 5。在仓库根目录下可通过如下命令运行本用例go test -run Test_Problem1482 ./leetcode/1482.Minimum-Number-of-Days-to-Make-m-Bouquets/本仓库的 go.mod 声明模块github.com/halfrost/LeetCode-GoGo 版本为go 1.19sort.Search在标准库中即可使用无需额外依赖。复杂度分析指标复杂度说明时间复杂度O(n · log(maxDay))二分约log2(maxDay) ≈ 30轮每轮O(n)线性扫描空间复杂度O(1)仅使用flowers、bouquets、maxDay等常数个变量在n 10^5、maxDay 10^9的极端数据下运算量约为10^5 × 30 3 × 10^6次运行开销极小这也是二分方案相比逐天模拟最坏10^9天的决定性优势。边界情况与易错点小结漏掉不可能的判断m*k n必须最先检查并返回-1否则二分会在无解区间上给出错误答案。答案区间上界务必取maxDay所有花盛开所需的最大天数而不是固定的大常数或m相关值示例 4 证明答案可以恰好等于maxDay。相邻语义未开的花会中断连续段flowers必须清零示例 3 专门考察这一点。二分谓词的返回方向sort.Search的谓词返回bouquets m可行返回的是第一个可行下标如果写反成 m得到的是最后一个不可行点结果会错一位。每朵花只能用一次flowers k成束后必须清零不能把同一朵花重复计入多束。举一反三同类最小化可行解问题本题是 LeetCode-Go 仓库中二分搜索专题的典型代表。仓库 leetcode 目录下还有大量适用同一范式的问题例如875. Koko Eating Bananas在[1, maxPile]上二分每小时吃香蕉的最少数量check 为总耗时是否 ≤ h1011. Capacity To Ship Packages Within D Days在[max(weights), sum(weights)]上二分最小载重check 为是否能在 D 天内运完1283. Find the Smallest Divisor Given a Threshold在除数区间上二分最小除数check 为商之和是否 ≤ threshold。这类题的共同特征解空间是某个范围上的整数、可行性随候选值单调变化、check 函数可在线性时间内完成。掌握先剪枝 二分 贪心 check三步法即可一通百通。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：1482. Minimum Number of Days to Make m Bouquets（二分搜索 + 贪心校验）
LeetCode-Go 题解1482. Minimum Number of Days to Make m Bouquets二分搜索 贪心校验【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 1482 题「制作 m 束花所需的最少天数」讲解如何用二分搜索 贪心线性校验在单调的解空间[0, maxDay]中快速定位满足条件的最小天数。这是最小化可行解minimize the feasible solution类题目的经典模板先判断可行性单调性再对有序区间二分。读完本文你将掌握这类等待天数 / 分配资源问题从建模、可行性判定到 Go 实现的完整套路并可直接复用本仓库 leetcode/1482.Minimum-Number-of-Days-to-Make-m-Bouquets 中的源码与测试用例进行验证。题目理解给定一个整数数组bloomDay以及两个整数m和k。花园中共有n朵花第i朵花会在第bloomDay[i]天盛开且恰好只能用于一束花。制作一束花需要使用花园中相邻的k朵花。要求返回从花园中摘下m束花所需等待的最少天数如果无法摘到m束花返回-1。关键约束来自题目与 README.md参数约束范围含义bloomDay.length n1 n 10^5花园中花的数量bloomDay[i]1 bloomDay[i] 10^9第 i 朵花的盛开天数m1 m 10^6需要制作的花束数量k1 k n每束花需要的相邻花朵数示例演练示例 1答案落在中间某天Input: bloomDay [1,10,3,10,2], m 3, k 1 Output: 3每束花只需 1 朵花因此开花即可成束。逐天观察x表示已盛开_表示未盛开第 1 天[x, _, _, _, _]只能制作 1 束第 2 天[x, _, _, _, x]只能制作 2 束第 3 天[x, _, x, _, x]可以制作 3 束。答案即第 3 天。示例 2花朵总数不足返回 -1Input: bloomDay [1,10,3,10,2], m 3, k 2 Output: -1需要3 × 2 6朵花但花园只有 5 朵花无论等多久都不可能完成直接返回-1。示例 3强调相邻条件Input: bloomDay [7,7,7,7,12,7,7], m 2, k 3 Output: 12第 7 天[x, x, x, x, _, x, x]前 3 朵相邻可组成 1 束最后 2 朵虽已开但数量不足 3且中间被未开的花隔断不能与前面的花组成一束第 12 天[x, x, x, x, x, x, x]全部盛开可以组成 2 束。答案即第 12 天。示例 4等待最久的天数Input: bloomDay [1000000000,1000000000], m 1, k 1 Output: 1000000000需要等待 10^9 天才能得到一束花说明答案可以取到bloomDay的最大值。示例 5交错花期Input: bloomDay [1,10,2,9,3,8,4,7,5,6], m 4, k 2 Output: 9m × k 8 ≤ n 10可行在解空间内二分第 9 天是第一个能凑齐 4 束花的天数。解题思路为什么可以用二分搜索解空间单调且有序等待天数d越大已盛开的花只会越多或不变可制作的花束数f(d)随d单调不减。因此答案区间一定落在[0, maxDay]maxDay为bloomDay中的最大值并且存在某个阈值ans使得d ans时f(d) md ≥ ans时f(d) ≥ m在这个有序解空间上可以用二分搜索找到第一个满足f(d) ≥ m的下标它即是最少天数。这正是最小化可行解类二分问题的标准特征可行性判定是单调的解空间边界确定。可行性判定check 函数贪心线性扫描对给定的候选天数days从左到右遍历bloomDay若bloomDay[i] days该花未开当前连续段中断flowers清零否则该花已开flowers一旦flowers k立即组成一束bouquets并清零重新计数——因为每朵花恰好只能用一次贪心地在满足相邻条件时立刻成束不会让结果变差遍历结束后若bouquets m说明在days天内可行。整个check是O(n)的线性扫描配合二分后总复杂度为O(n · log maxDay)在n ≤ 10^5、maxDay ≤ 10^9的量级下完全可行。代码实现本仓库的完整实现位于 1482. Minimum Number of Days to Make m Bouquets.go与 README.md 中给出的代码一致如下已补充注释package leetcode import sort func minDays(bloomDay []int, m int, k int) int { // 剪枝需要的花朵总数超过花园容量直接判定不可能 if m*k len(bloomDay) { return -1 } // 求解空间上界所有花都盛开的天数 maxDay : 0 for _, day : range bloomDay { if day maxDay { maxDay day } } // 在 [0, maxDay] 中二分找到第一个满足 bouquets m 的天数 return sort.Search(maxDay, func(days int) bool { flowers, bouquets : 0, 0 for _, d : range bloomDay { if d days { // 未盛开中断连续段 flowers 0 } else { // 已盛开累加连续花朵数凑满 k 朵即成一束 flowers if flowers k { bouquets flowers 0 } } } return bouquets m }) }实现细节说明先剪枝再二分m*k len(bloomDay)时无论等多久都不够花直接返回-1省去无意义的搜索也天然规避了示例 2 这类情形。二分区间[0, maxDay]上界取bloomDay最大值保证存在可行解时答案一定落在区间内sort.Search返回的是满足谓词的第一个索引正好对应最少天数。谓词单调性保证正确性sort.Search要求f(0..i-1) false且f(i..n-1) true而天数越多花束越多恰好满足这一前提。贪心成束的正确性flowers达到k立即成束并清零等价于把每个连续已开区间按长度k切块区间长度为L时可产出的花束数恰为L/k向下取整不会少算也不会多算。测试用例与运行验证本仓库为本题提供了与题目示例一一对应的单元测试位于 1482. Minimum Number of Days to Make m Bouquets_test.gofunc Test_Problem1482(t *testing.T) { qs : []question1482{ {para1482{[]int{1, 10, 3, 10, 2}, 3, 1}, ans1482{3}}, {para1482{[]int{1, 10, 3, 10, 2}, 3, 2}, ans1482{-1}}, {para1482{[]int{7, 7, 7, 7, 12, 7, 7}, 2, 3}, ans1482{12}}, {para1482{[]int{1000000000, 1000000000}, 1, 1}, ans1482{1000000000}}, {para1482{[]int{1, 10, 2, 9, 3, 8, 4, 7, 5, 6}, 4, 2}, ans1482{9}}, } // 逐条断言 minDays(p.bloomDay, p.m, p.k) 与期望答案一致 ... }测试覆盖了五类典型场景答案在中间示例 1、不可能完成返回-1示例 2、相邻性约束示例 3、答案取最大值示例 4以及交替花期的中等规模用例示例 5。在仓库根目录下可通过如下命令运行本用例go test -run Test_Problem1482 ./leetcode/1482.Minimum-Number-of-Days-to-Make-m-Bouquets/本仓库的 go.mod 声明模块github.com/halfrost/LeetCode-GoGo 版本为go 1.19sort.Search在标准库中即可使用无需额外依赖。复杂度分析指标复杂度说明时间复杂度O(n · log(maxDay))二分约log2(maxDay) ≈ 30轮每轮O(n)线性扫描空间复杂度O(1)仅使用flowers、bouquets、maxDay等常数个变量在n 10^5、maxDay 10^9的极端数据下运算量约为10^5 × 30 3 × 10^6次运行开销极小这也是二分方案相比逐天模拟最坏10^9天的决定性优势。边界情况与易错点小结漏掉不可能的判断m*k n必须最先检查并返回-1否则二分会在无解区间上给出错误答案。答案区间上界务必取maxDay所有花盛开所需的最大天数而不是固定的大常数或m相关值示例 4 证明答案可以恰好等于maxDay。相邻语义未开的花会中断连续段flowers必须清零示例 3 专门考察这一点。二分谓词的返回方向sort.Search的谓词返回bouquets m可行返回的是第一个可行下标如果写反成 m得到的是最后一个不可行点结果会错一位。每朵花只能用一次flowers k成束后必须清零不能把同一朵花重复计入多束。举一反三同类最小化可行解问题本题是 LeetCode-Go 仓库中二分搜索专题的典型代表。仓库 leetcode 目录下还有大量适用同一范式的问题例如875. Koko Eating Bananas在[1, maxPile]上二分每小时吃香蕉的最少数量check 为总耗时是否 ≤ h1011. Capacity To Ship Packages Within D Days在[max(weights), sum(weights)]上二分最小载重check 为是否能在 D 天内运完1283. Find the Smallest Divisor Given a Threshold在除数区间上二分最小除数check 为商之和是否 ≤ threshold。这类题的共同特征解空间是某个范围上的整数、可行性随候选值单调变化、check 函数可在线性时间内完成。掌握先剪枝 二分 贪心 check三步法即可一通百通。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考