LeetCode 每日一题笔记 日期：2025.12.01 题目：2141.同时运行 N 台电脑的最长时间

LeetCode 每日一题笔记0. 前言日期2025.12.01题目2141.同时运行 N 台电脑的最长时间难度困难标签数组 二分查找 贪心1. 题目理解问题描述有n台电脑给定整数数组batteries第i个电池可让一台电脑运行batteries[i]分钟。初始时每台电脑最多连一个电池之后可随时断开/连接电池无时间消耗。要求让全部n台电脑同时运行返回最长运行分钟数。示例示例 1输入n 2, batteries [3,3,3]输出4解释总电池容量 92台电脑同时运行的理论最大时间为 9/24.5实际可运行 4 分钟每个电池贡献 3 分钟总和 9 ≥ 2×48。示例 2输入n 3, batteries [10,10,3,5]输出8解释总容量 28理论最大 28/3≈9.33实际验证 8 分钟可行各电池贡献 8、8、3、5总和 24 ≥ 3×824。2. 解题思路核心观察若要让n台电脑同时运行T分钟总能耗为n×T需满足所有电池的有效贡献总和 ≥ n×T每个电池的有效贡献为min(电池容量, T)电池最多为某台电脑提供T分钟电量。算法步骤二分范围确定左边界left 0最小运行时间右边界right 总电池容量 / n理论最大运行时间总能耗不能超过总电池容量。二分查找取中间值mid作为候选运行时间验证mid是否可行计算所有电池的有效贡献总和判断是否 ≥ n×mid若可行记录mid并尝试更大时间右移左边界若不可行尝试更小时间左移右边界。3. 代码实现classSolution{publiclongmaxRunTime(intn,int[]batteries){// 计算所有电池总容量用long避免溢出longsum0;for(intb:batteries)sumb;// 二分查找的范围longleft0,rightsum/n;longans0;while(leftright){longmid(leftright)/2;// 验证mid分钟是否可行if(check(mid,n,batteries)){ansmid;// 记录可行的最大时间leftmid1;// 尝试更大时间}else{rightmid-1;// 尝试更小时间}}returnans;}// 验证函数判断是否能让n台电脑同时运行T分钟privatebooleancheck(longT,intn,int[]batteries){longtotal0;for(intb:batteries){totalMath.min(b,T);// 每个电池最多贡献T分钟if(totaln*T)returntrue;// 提前终止节省时间}returntotaln*T;}}4. 代码优化说明优化版将验证逻辑内联到二分循环中减少函数调用开销仅逻辑合并核心思路不变classSolution{publiclongmaxRunTime(intn,int[]batteries){longsum0;for(intcap:batteries){sumcap;}longleft0,rightsum/n,ans0;while(leftright){longmidleft(right-left)/2;// 避免leftright溢出longtotal0;for(intcap:batteries){totalMath.min(cap,mid);}if(totaln*mid){ansmid;leftmid1;}else{rightmid-1;}}returnans;}}5. 复杂度分析时间复杂度(O(m \times \log(\text{sum}/n)))m是电池数量每次验证需遍历所有电池(O(m))二分查找的次数为 (\log(\text{sum}/n))sum为总电池容量。空间复杂度(O(1))仅使用常量级额外空间。6. 总结核心思路是二分查找 贪心验证通过二分缩小运行时间的候选范围用贪心计算电池有效贡献来验证可行性关键技巧是利用“每个电池最多贡献T分钟”的贪心策略快速判断候选时间是否可行该方法高效解决了“最大化同时运行时间”的问题避免了暴力枚举的高时间复杂度。