LeetCode 1011 详解二分答案 贪心模拟求解 D 天内送达包裹的最低船运能力【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇围绕 LeetCode 1011「Capacity to Ship Packages Within D Days在 D 天内送达包裹的能力」展开以articles/capacity-to-ship-packages-within-d-days.md为核心骨架结合本仓库中 Python、C、Java、Kotlin 四份源码实现进行纵深印证。读完本文你将掌握「在单调答案空间上二分 贪心模拟校验」这一经典题型的完整解法从最朴素的线性枚举到 O(n log n) 的二分答案再到边界条件与常见陷阱的排查可直接迁移到分割数组最大和吃掉香蕉的珂珂等同类问题。一、题目背景与问题定义给定一个整数数组weights其中weights[i]表示传送带上第i个包裹的重量包裹必须按给定顺序装船每天最多装载days天内的货。要求计算能够将所有包裹在days天内送达的最小船运能力capacity。能力值表示一艘船单次能承载的最大总重量。关键约束有两层顺序约束包裹必须按weights的顺序装载不能打乱次序这正是贪心模拟可行的前提最小化目标在能在days天内运完的所有合法能力中取最小值。本仓库在 README.md 的题目索引中登记了该题编号 1011并提供多语言题解。仓库中实现的统一函数签名如下语言文件函数签名Pythonpython/1011-capacity-to-ship-packages-within-d-days.pyshipWithinDays(weights: List[int], days: int) - intCcpp/1011-capacity-to-ship-packages-within-d-days.cppint shipWithinDays(vectorint weights, int days)Javajava/1011-capacity-to-ship-packages-within-d-days.javaint shipWithinDays(int[] weights, int days)Kotlinkotlin/1011-capacity-to-ship-packages-within-d-days.ktfun shipWithinDays(weights: IntArray, days: Int): Int二、前置知识在动手编码之前先确认你具备以下三项能力它们是本题两种解法的共同地基二分搜索Binary Search在一个单调的答案空间上搜索最优值。本题的核心洞察是能力越大所需天数越少答案空间天然单调贪心模拟Greedy Simulation给定一个候选能力用贪心策略当前船能装就装装不下才换新船模拟装船过程从而验证该候选值是否可行问题分解Problem Decomposition把求最小能力这一优化问题拆解为给定能力能否在限期内运完这一系列的可行性判断feasibility check子问题。三、解法一线性搜索Linear Search3.1 直觉最小可行船运能力至少等于最重包裹的重量——否则那个包裹永远装不上任何一艘船。以此为起点从max(weights)开始逐个能力值尝试每次模拟装船过程检查能否在days天内运完。第一个可行且最小的能力值即为答案。由于答案空间是单调的能力越大越容易满足因此一旦某个能力可行它就是当前能找到的最小可行值直接返回即可。3.2 算法步骤初始化结果res为数组中的最大重量理论最小能力对当前能力res模拟装船维护当前船的剩余容量cap遍历包裹若当前包裹放不进cap - w 0则开一艘新船ships并把cap重置为res无论如何装下当前包裹cap - w若使用的船数ships days说明该能力可行返回res否则能力res加 1回到步骤 2 继续尝试。3.3 多语言实现以下实现覆盖仓库支持的 9 种语言逻辑完全一致tabs结构在纯 Markdown 下以语言小节呈现Pythonclass Solution: def shipWithinDays(self, weights: List[int], days: int) - int: res max(weights) while True: ships 1 cap res for w in weights: if cap - w 0: ships 1 cap res cap - w if ships days: return res res 1Javapublic class Solution { public int shipWithinDays(int[] weights, int days) { int res 0; for (int weight : weights) { res Math.max(res, weight); } while (true) { int ships 1; int cap res; for (int weight : weights) { if (cap - weight 0) { ships; cap res; } cap - weight; } if (ships days) { return res; } res; } } }Cclass Solution { public: int shipWithinDays(vectorint weights, int days) { int res *max_element(weights.begin(), weights.end()); while (true) { int ships 1, cap res; for (int w : weights) { if (cap - w 0) { ships; cap res; } cap - w; } if (ships days) { return res; } res; } } };JavaScriptclass Solution { /** * param {number[]} weights * param {number} days * return {number} */ shipWithinDays(weights, days) { let res Math.max(...weights); while (true) { let ships 1, cap res; for (let w of weights) { if (cap - w 0) { ships; cap res; } cap - w; } if (ships days) { return res; } res; } } }C#public class Solution { public int ShipWithinDays(int[] weights, int days) { int res weights.Max(); while (true) { int ships 1; int cap res; foreach (int w in weights) { if (cap - w 0) { ships; cap res; } cap - w; } if (ships days) { return res; } res; } } }Gofunc shipWithinDays(weights []int, days int) int { res : 0 for _, w : range weights { if w res { res w } } for { ships : 1 cap : res for _, w : range weights { if cap-w 0 { ships cap res } cap - w } if ships days { return res } res } }Kotlinclass Solution { fun shipWithinDays(weights: IntArray, days: Int): Int { var res weights.max() while (true) { var ships 1 var cap res for (w in weights) { if (cap - w 0) { ships cap res } cap - w } if (ships days) { return res } res } } }Swiftclass Solution { func shipWithinDays(_ weights: [Int], _ days: Int) - Int { var res weights.max()! while true { var ships 1 var cap res for w in weights { if cap - w 0 { ships 1 cap res } cap - w } if ships days { return res } res 1 } } }Rustimpl Solution { pub fn ship_within_days(weights: Veci32, days: i32) - i32 { let mut res *weights.iter().max().unwrap(); loop { let mut ships 1; let mut cap res; for w in weights { if cap - w 0 { ships 1; cap res; } cap - w; } if ships days { return res; } res 1; } } }3.4 复杂度分析时间复杂度$O(n^2)$ —— 最坏情况下能力从max(weights)一路递增到sum(weights)共 $O(n)$ 个候选值每个候选值都要 $O(n)$ 遍历一次数组空间复杂度$O(1)$ —— 仅使用常数个变量无额外数据结构。当weights数值较大如 $10^5$ 级别时$O(n^2)$ 会超时必须切换到解法二的二分搜索。四、解法二二分搜索Binary Search4.1 直觉线性枚举效率低但答案空间具备单调性这一关键性质若某个能力可行则任何更大的能力也一定可行更大的船总能装下同样的货物分配方案。因此可以在答案空间上直接二分。搜索空间的两端非常明确下界leftmax(weights)能力至少能装下最重包裹上界rightsum(weights)一天把所有包裹装完。对每个中点能力mid调用贪心模拟判断其是否可行再据此收缩搜索区间最终收敛到最小可行能力。4.2 算法步骤设定二分区间left max(weights)right sum(weights)当left right时循环计算mid (left right) / 2用贪心模拟校验能力mid是否能在days天内运完所有包裹若可行则更新结果为min(res, mid)并搜索左半区间right mid - 1尝试寻找更小的可行能力若不可行则搜索右半区间left mid 1返回过程中记录的最小可行能力。其中贪心模拟canShip(cap)的细节与线性解法完全一致ships从 1 开始计数第一天currCap表示当前船的剩余容量遇到装不下的包裹就ships并重置currCap cap一旦ships days立即返回false提前剪枝。4.3 多语言实现Pythonclass Solution: def shipWithinDays(self, weights: List[int], days: int) - int: l, r max(weights), sum(weights) res r def canShip(cap): ships, currCap 1, cap for w in weights: if currCap - w 0: ships 1 if ships days: return False currCap cap currCap - w return True while l r: cap (l r) // 2 if canShip(cap): res min(res, cap) r cap - 1 else: l cap 1 return resJavapublic class Solution { public int shipWithinDays(int[] weights, int days) { int l 0, r 0; for (int w : weights) { l Math.max(l, w); r w; } int res r; while (l r) { int cap (l r) / 2; if (canShip(weights, days, cap)) { res Math.min(res, cap); r cap - 1; } else { l cap 1; } } return res; } private boolean canShip(int[] weights, int days, int cap) { int ships 1, currCap cap; for (int w : weights) { if (currCap - w 0) { ships; if (ships days) { return false; } currCap cap; } currCap - w; } return true; } }Cclass Solution { public: int shipWithinDays(vectorint weights, int days) { int l *max_element(weights.begin(), weights.end()); int r accumulate(weights.begin(), weights.end(), 0); int res r; while (l r) { int cap (l r) / 2; if (canShip(weights, days, cap)) { res min(res, cap); r cap - 1; } else { l cap 1; } } return res; } private: bool canShip(const vectorint weights, int days, int cap) { int ships 1, currCap cap; for (int w : weights) { if (currCap - w 0) { ships; if (ships days) { return false; } currCap cap; } currCap - w; } return true; } };JavaScriptclass Solution { /** * param {number[]} weights * param {number} days * return {number} */ shipWithinDays(weights, days) { let l Math.max(...weights); let r weights.reduce((a, b) a b, 0); let res r; const canShip (cap) { let ships 1, currCap cap; for (const w of weights) { if (currCap - w 0) { ships; if (ships days) { return false; } currCap cap; } currCap - w; } return true; }; while (l r) { const cap Math.floor((l r) / 2); if (canShip(cap)) { res Math.min(res, cap); r cap - 1; } else { l cap 1; } } return res; } }C#public class Solution { public int ShipWithinDays(int[] weights, int days) { int l weights.Max(); int r weights.Sum(); int res r; bool CanShip(int cap) { int ships 1; int currCap cap; foreach (int w in weights) { if (currCap - w 0) { ships; if (ships days) return false; currCap cap; } currCap - w; } return true; } while (l r) { int cap (l r) / 2; if (CanShip(cap)) { res Math.Min(res, cap); r cap - 1; } else { l cap 1; } } return res; } }Gofunc shipWithinDays(weights []int, days int) int { l, r : 0, 0 for _, w : range weights { if w l { l w } r w } res : r canShip : func(cap int) bool { ships, currCap : 1, cap for _, w : range weights { if currCap-w 0 { ships if ships days { return false } currCap cap } currCap - w } return true } for l r { cap : (l r) / 2 if canShip(cap) { if cap res { res cap } r cap - 1 } else { l cap 1 } } return res }Kotlinclass Solution { fun shipWithinDays(weights: IntArray, days: Int): Int { var l weights.max() var r weights.sum() var res r fun canShip(cap: Int): Boolean { var ships 1 var currCap cap for (w in weights) { if (currCap - w 0) { ships if (ships days) return false currCap cap } currCap - w } return true } while (l r) { val cap (l r) / 2 if (canShip(cap)) { res minOf(res, cap) r cap - 1 } else { l cap 1 } } return res } }Swiftclass Solution { func shipWithinDays(_ weights: [Int], _ days: Int) - Int { var l weights.max()! var r weights.reduce(0, ) var res r func canShip(_ cap: Int) - Bool { var ships 1 var currCap cap for w in weights { if currCap - w 0 { ships 1 if ships days { return false } currCap cap } currCap - w } return true } while l r { let cap (l r) / 2 if canShip(cap) { res min(res, cap) r cap - 1 } else { l cap 1 } } return res } }Rustimpl Solution { pub fn ship_within_days(weights: Veci32, days: i32) - i32 { let mut l *weights.iter().max().unwrap(); let mut r: i32 weights.iter().sum(); let mut res r; let can_ship |cap: i32| - bool { let mut ships 1; let mut curr_cap cap; for w in weights { if curr_cap - w 0 { ships 1; if ships days { return false; } curr_cap cap; } curr_cap - w; } true }; while l r { let cap (l r) / 2; if can_ship(cap) { res res.min(cap); r cap - 1; } else { l cap 1; } } res } }4.4 复杂度分析时间复杂度$O(n \log n)$ —— 二分区间宽度为 $O(n)$sum(weights) - max(weights)共 $O(\log n)$ 轮每轮canShip需 $O(n)$ 遍历一次数组空间复杂度$O(1)$ —— 与线性解法相同只占用常数空间。五、仓库源码印证边界优化与实现差异二分解法在本仓库的四份源码中均有落地且实现细节略有差异值得对照学习5.1 标准二分实现Python 实现 与原文档的二分解法逐行一致以max(weights)、sum(weights)为区间端点canShip内以ships days作为可行性判据主循环l r可行时收缩右边界并维护min_cap。5.2 下界收紧优化l max(l, r / days)Java 实现 在第 20-21 行额外做了一步下界收紧//We can improve lower bound by taking max of the average capacity and max weight l Math.max(l, r/days);其依据是days天内平均每天至少需要运sum(weights) / days的重量因此下界可以收紧为max(max(weights), sum(weights) / days)。这一步不会改变正确性真正的答案必然不小于该下界却能缩小二分区间、减少迭代轮数是一个值得吸收的工程优化点。5.3 提前剪枝与返回形式差异C 实现 将canShipWithinDays独立为私有成员函数通过当前包裹与下一个包裹之和超过容量才换船的视角实现模拟并同样在answer上维护最小可行值Kotlin 实现 走的是不显式维护res二分结束后直接返回left的写法——因为循环退出时left恰好指向第一个可行值这是二分求最小可行解的另一种等价表达。四种实现最终都收敛到同一答案差异仅在于编码风格与微优化印证了原文档算法的普适性。六、常见陷阱Common Pitfalls6.1 二分边界设置错误最小能力必须至少是max(weights)否则最重包裹永远装不上船最大能力为sum(weights)一天装完。若从 0 或 1 开始会导致区间内存在大量非法状态——某些包裹在那些能力下根本无法装载白白浪费迭代次数甚至因溢出/边界问题出错。# Wrong: minimum capacity too low l, r 1, sum(weights) # Should be: l max(weights)正确写法是l, r max(weights), sum(weights)6.2 模拟中天数计数错误常见错误包括漏算第一天、或者换船的时机不对。正确语义是第 1 天一开始就有一艘容量为cap的空船可用只有当当前包裹装不进当前这艘船时才开新船并进入下一天。因此ships初始值必须是 1而不是 0换船时ships且currCap重置为cap随后再把当前包裹装入新船。6.3 二分判定条件用反本题属于典型的寻找满足条件的最小值find minimum satisfying condition问题当canShip(cap)为true当前能力可行时应搜索左半区间r cap - 1继续试探更小的可行能力当canShip(cap)为false时才搜索右半区间l cap 1。若把两者写反最终返回的将是最大可行能力附近的值得到次优偏大答案。判据口诀可行向左收不可行向右扩同时用res记录每次可行时的最小值。七、总结本题是二分答案 贪心模拟校验范式最经典的入门题之一维度线性搜索二分搜索核心思路从最小能力逐个枚举在单调答案空间上折半收缩时间复杂度$O(n^2)$$O(n \log n)$空间复杂度$O(1)$$O(1)$适用场景数据规模小、便于理解大规模数据竞赛与面试标准解法解题链路可以概括为三步确定答案的单调性 → 圈定合法搜索区间[max(weights), sum(weights)]→ 用贪心模拟充当可行性校验器。这一模式可无缝迁移到分割数组的最大值最小化Koko 吃香蕉制作花束的最少天数等一大批二分答案题目。仓库内的四份多语言实现Python、C、Java、Kotlin可作为对照基准帮助你在任意熟悉的语言中快速复现并验证这一解法。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考