LeetCode 3296. 移山所需的最少秒数 技术解析（含完整可运行代码）

摘要本文针对LeetCode 3296题“移山所需的最少秒数”从问题本质出发拆解题意、分析核心痛点推导最优解题思路二分查找详细讲解算法原理、边界处理及代码实现细节结合示例验证算法正确性同时分析时间复杂度与空间复杂度给出优化方向帮助开发者快速理解并掌握该题的解题逻辑适配面试、算法练习等场景。一、问题核心解析1.1 题目题意拆解题目核心需求给定山的高度mountainHeight和工人们的工作时间数组workerTimes工人们同时工作将山的高度降至0求最少所需秒数。关键规则重点理解工人i降低山的高度x所需时间为workerTimes[i] * (1 2 ... x) workerTimes[i] * x*(x1)/2等差数列求和公式核心推导点所有工人同时工作总耗时取所有工人各自耗时的最大值因为需等耗时最长的工人完成整体才算结束目标分配每个工人需要降低的高度所有工人降低的高度总和 ≥ mountainHeight使得所有工人的耗时最大值最小化。1.2 核心痛点与解题关键痛点1直接暴力分配高度枚举所有可能的分配方式时间复杂度极高无法适配mountainHeight≤1e5和workerTimes长度≤1e4的约束痛点2工人耗时与降低高度呈二次函数关系x*(x1)/2分配高度时需平衡各工人的耗时避免单个工人耗时过高解题关键二分查找。将“求最少耗时”转化为“判断某一耗时T是否能完成移山”通过二分枚举T的可能值找到最小的满足条件的T。二、解题思路推导二分查找核心逻辑2.1 二分查找的可行性分析二分查找的前提是“单调性”本题满足单调性若耗时T能完成移山则所有大于T的耗时也一定能完成只需减少部分工人的降低高度总耗时不会增加若耗时T不能完成移山则所有小于T的耗时也一定不能完成时间不足无法让所有工人完成足够的高度降低。2.2 二分查找的边界确定确定二分查找的左边界left和右边界right缩小枚举范围左边界left最小可能耗时初始为0理论上的最小值实际需满足至少能完成移山右边界right最大可能耗时即“单个工人完成所有移山工作”的耗时最坏情况只有一个工人计算公式为workerTimes[max_idx] * mountainHeight*(mountainHeight1)/2max_idx为workerTimes中最大值的索引。2.3 核心判断函数check函数对于给定的耗时T判断所有工人在T时间内最多能共同降低的山的高度总和是否 ≥ mountainHeight。关键推导单个工人的最大降低高度设工人i在时间T内最多能降低x高度则满足workerTimes[i] * x*(x1)/2 ≤ T。变形可得x² x - 2*T/workerTimes[i] ≤ 0。解这个一元二次方程取正根的整数部分因为x必须是正整数即x floor( (sqrt(1 8*T/workerTimes[i]) - 1) / 2 )。遍历所有工人计算每个工人的最大降低高度x求和后与mountainHeight比较若总和 ≥ mountainHeight则T可行否则不可行。2.4 二分查找完整流程初始化left0right单个工人完成所有工作的最大耗时当left right时计算mid (left right) // 2调用check(mid)判断mid时间是否能完成移山若能完成说明mid可能是最优解缩小右边界right mid若不能完成说明时间不足扩大左边界left mid 1循环结束后left或right即为最少所需秒数。三、算法实现Python贴合要求格式核心代码严格遵循题目要求的Solution类格式包含完整的check函数、二分查找逻辑注释详细可直接复制运行适配LeetCode提交规范。importmathclassSolution:defminNumberOfSeconds(self,mountainHeight:int,workerTimes:list[int])-int: 计算移山所需的最少秒数 :param mountainHeight: 山的初始高度 :param workerTimes: 工人们的工作时间数组workerTimes[i]表示工人i每单位高度的基础耗时 :return: 最少所需秒数 defcheck(T:int)-bool: 判断在耗时T内所有工人能否共同将山的高度降至0 :param T: 给定的耗时 :return: 能完成返回True否则返回False total0# 所有工人在T时间内最多能降低的总高度fortinworkerTimes:# 推导单个工人在T时间内最多能降低的高度x# 由 t * x*(x1)/2 ≤ T → x² x - 2*T/t ≤ 0# 解一元二次方程取正根的整数部分discriminant18*T//t# 判别式避免浮点数误差先整除x(math.isqrt(discriminant)-1)//2totalx# 剪枝总高度已满足无需继续计算其他工人iftotalmountainHeight:returnTruereturntotalmountainHeight# 确定二分查找的边界# 右边界单个工人完成所有工作的最大耗时最坏情况max_timemax(workerTimes)rightmax_time*mountainHeight*(mountainHeight1)//2left0# 二分查找核心逻辑whileleftright:mid(leftright)//2ifcheck(mid):# 耗时mid可行尝试更小的耗时rightmidelse:# 耗时mid不可行需要更大的耗时leftmid1returnleft四、代码细节解析与优化4.1 关键细节说明判别式计算优化使用8 * T // t而非8 * T / t避免浮点数精度误差确保后续开方计算的准确性开方函数选择使用math.isqrtPython 3.8用于计算非负整数的整数平方根比math.sqrt更高效且避免浮点数转换剪枝操作在check函数中当累计总高度≥mountainHeight时立即返回True无需遍历所有工人提升效率边界处理right的计算采用整数运算避免溢出Python无整数溢出问题但保持规范适配其他语言迁移。4.2 时间复杂度与空间复杂度分析时间复杂度O(n * logM)其中n为workerTimes的长度≤1e4M为二分查找的边界范围最大为1e6 * 1e5 * 1e5 1e16log2(1e16)≈53。整体计算量约为1e4 * 53 5.3e5完全满足题目约束空间复杂度O(1)仅使用常数级变量无额外空间开销。4.3 可能的优化方向针对极端场景如workerTimes中存在大量重复值可先对workerTimes进行去重减少check函数中的遍历次数进一步提升效率但在常规场景下原代码已足够高效无需额外优化。五、示例验证贴合题目示例验证算法正确性示例1输入mountainHeight4workerTimes[2,1,1]二分查找过程简述right max([2,1,1]) * 45//2 220//2 20left0mid(020)//210check(10)工人0可降x(sqrt(18*10/2)-1)/23工人1可降x4工人2可降x4总高度34411≥4可行right10持续二分最终收敛到leftright3与示例输出一致。示例2输入mountainHeight10workerTimes[3,2,2,4]验证当T12时check(12)工人0t3x(sqrt(1812/3)-1)/2(sqrt(33)-1)/2≈2耗时32*3//29≤12工人1t2x(sqrt(1812/2)-1)/2(sqrt(49)-1)/23耗时23*4//212≤12工人2t2同工人1x3工人3t4x(sqrt(1812/4)-1)/2(sqrt(25)-1)/22耗时42*3//212≤12总高度233210≥10可行且无更小的T满足条件输出12与示例一致。示例3输入mountainHeight5workerTimes[1]验证right156//215二分查找最终收敛到15与示例输出一致。六、常见错误与注意事项错误1忽略“工人同时工作总耗时取最大值”的规则误将所有工人耗时求和作为总耗时错误2推导单个工人最大降低高度时未使用等差数列求和公式导致公式错误如写成tx而非tx*(x1)/2错误3二分查找边界设置过小导致无法找到可行解如right未取单个工人的最大耗时错误4使用浮点数开方后未取整导致x计算错误如未用floor或整数除法。七、总结本题的核心是将“最小化最大耗时”的优化问题通过二分查找转化为“可行性判断”的问题核心难点在于理解工人耗时与降低高度的二次关系并推导单个工人最大降低高度的计算公式。本文实现的代码严格遵循题目要求逻辑严谨、细节优化到位可直接提交LeetCode通过所有测试用例。同时二分查找的思路可迁移到类似“最小化最大成本”“最大化最小收益”的优化问题中具有较强的通用性。对于初学者建议重点掌握“二分查找可行性判断”的解题框架理解check函数的推导过程明确二分边界的确定方法逐步提升对优化类算法的解题能力。