当前位置：首页 > news >正文

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

news 2026/5/11 23:39:30

摘要：本文针对LeetCode 3296题“移山所需的最少秒数”，从问题本质出发，拆解题意、分析核心痛点，推导最优解题思路（二分查找），详细讲解算法原理、边界处理及代码实现细节，结合示例验证算法正确性，同时分析时间复杂度与空间复杂度，给出优化方向，帮助开发者快速理解并掌握该题的解题逻辑，适配面试、算法练习等场景。

一、问题核心解析

1.1 题目题意拆解

题目核心需求：给定山的高度mountainHeight和工人们的工作时间数组workerTimes，工人们同时工作，将山的高度降至0，求最少所需秒数。

关键规则（重点理解）：

工人i降低山的高度x，所需时间为workerTimes[i] * (1 + 2 + ... + x) = workerTimes[i] * x*(x+1)/2（等差数列求和公式，核心推导点）；
所有工人同时工作，总耗时取所有工人各自耗时的最大值（因为需等耗时最长的工人完成，整体才算结束）；
目标：分配每个工人需要降低的高度（所有工人降低的高度总和 ≥ mountainHeight），使得所有工人的耗时最大值最小化。

1.2 核心痛点与解题关键

痛点1：直接暴力分配高度（枚举所有可能的分配方式），时间复杂度极高，无法适配mountainHeight（≤1e5）和workerTimes长度（≤1e4）的约束；

痛点2：工人耗时与降低高度呈二次函数关系（x*(x+1)/2），分配高度时需平衡各工人的耗时，避免单个工人耗时过高；

解题关键：二分查找。将“求最少耗时”转化为“判断某一耗时T是否能完成移山”，通过二分枚举T的可能值，找到最小的满足条件的T。

二、解题思路推导（二分查找核心逻辑）

2.1 二分查找的可行性分析

二分查找的前提是“单调性”，本题满足单调性：

若耗时T能完成移山，则所有大于T的耗时也一定能完成（只需减少部分工人的降低高度，总耗时不会增加）；
若耗时T不能完成移山，则所有小于T的耗时也一定不能完成（时间不足，无法让所有工人完成足够的高度降低）。

2.2 二分查找的边界确定

确定二分查找的左边界left和右边界right，缩小枚举范围：

左边界left：最小可能耗时，初始为0（理论上的最小值，实际需满足至少能完成移山）；
右边界right：最大可能耗时，即“单个工人完成所有移山工作”的耗时（最坏情况，只有一个工人），计算公式为workerTimes[max_idx] * mountainHeight*(mountainHeight+1)/2（max_idx为workerTimes中最大值的索引）。

2.3 核心判断函数（check函数）

对于给定的耗时T，判断所有工人在T时间内，最多能共同降低的山的高度总和是否 ≥ mountainHeight。

关键推导（单个工人的最大降低高度）：

设工人i在时间T内最多能降低x高度，则满足workerTimes[i] * x*(x+1)/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 二分查找完整流程

初始化left=0，right=单个工人完成所有工作的最大耗时；
当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 """total=0# 所有工人在T时间内最多能降低的总高度fortinworkerTimes:# 推导单个工人在T时间内最多能降低的高度x# 由 t * x*(x+1)/2 ≤ T → x² + x - 2*T/t ≤ 0# 解一元二次方程，取正根的整数部分discriminant=1+8*T//t# 判别式，避免浮点数误差，先整除x=(math.isqrt(discriminant)-1)//2total+=x# 剪枝：总高度已满足，无需继续计算其他工人iftotal>=mountainHeight:returnTruereturntotal>=mountainHeight# 确定二分查找的边界# 右边界：单个工人完成所有工作的最大耗时（最坏情况）max_time=max(workerTimes)right=max_time*mountainHeight*(mountainHeight+1)//2left=0# 二分查找核心逻辑whileleft<right:mid=(left+right)//2ifcheck(mid):# 耗时mid可行，尝试更小的耗时right=midelse:# 耗时mid不可行，需要更大的耗时left=mid+1returnleft

四、代码细节解析与优化

4.1 关键细节说明

判别式计算优化：使用8 * T // t而非8 * T / t，避免浮点数精度误差，确保后续开方计算的准确性；
开方函数选择：使用math.isqrt（Python 3.8+），用于计算非负整数的整数平方根，比math.sqrt更高效，且避免浮点数转换；
剪枝操作：在check函数中，当累计总高度≥mountainHeight时，立即返回True，无需遍历所有工人，提升效率；
边界处理：right的计算采用整数运算，避免溢出（Python无整数溢出问题，但保持规范，适配其他语言迁移）。

4.2 时间复杂度与空间复杂度分析

时间复杂度：O(n * logM)，其中n为workerTimes的长度（≤1e4），M为二分查找的边界范围（最大为1e6 * 1e5 * 1e5 = 1e16，log2(1e16)≈53）。整体计算量约为1e4 * 53 = 5.3e5，完全满足题目约束；
空间复杂度：O(1)，仅使用常数级变量，无额外空间开销。

4.3 可能的优化方向

针对极端场景（如workerTimes中存在大量重复值），可先对workerTimes进行去重，减少check函数中的遍历次数，进一步提升效率；但在常规场景下，原代码已足够高效，无需额外优化。

五、示例验证（贴合题目示例，验证算法正确性）

示例1：输入mountainHeight=4，workerTimes=[2,1,1]

二分查找过程简述：

right = max([2,1,1]) * 45//2 = 220//2 = 20，left=0；
mid=(0+20)//2=10，check(10)：工人0可降x=(sqrt(1+8*10/2)-1)/2=3，工人1可降x=4，工人2可降x=4，总高度3+4+4=11≥4，可行，right=10；
持续二分，最终收敛到left=right=3，与示例输出一致。