LeetCode 每日一题笔记
0. 前言
- 日期：2025.12.01
- 题目：2141.同时运行 N 台电脑的最长时间
- 难度：困难
- 标签：数组 二分查找 贪心
1. 题目理解
问题描述：
有n台电脑，给定整数数组batteries（第i个电池可让一台电脑运行batteries[i]分钟）。初始时每台电脑最多连一个电池，之后可随时断开/连接电池（无时间消耗）。要求让全部n台电脑同时运行，返回最长运行分钟数。
示例：
示例 1：
输入：n = 2, batteries = [3,3,3]
输出：4
解释：总电池容量 9，2台电脑同时运行的理论最大时间为 9/2=4.5，实际可运行 4 分钟（每个电池贡献 3 分钟，总和 9 ≥ 2×4=8）。
示例 2：
输入：n = 3, batteries = [10,10,3,5]
输出：8
解释：总容量 28，理论最大 28/3≈9.33，实际验证 8 分钟可行（各电池贡献 8、8、3、5，总和 24 ≥ 3×8=24）。
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避免溢出）longsum=0;for(intb:batteries)sum+=b;// 二分查找的范围longleft=0,right=sum/n;longans=0;while(left<=right){longmid=(left+right)/2;// 验证mid分钟是否可行if(check(mid,n,batteries)){ans=mid;// 记录可行的最大时间left=mid+1;// 尝试更大时间}else{right=mid-1;// 尝试更小时间}}returnans;}// 验证函数：判断是否能让n台电脑同时运行T分钟privatebooleancheck(longT,intn,int[]batteries){longtotal=0;for(intb:batteries){total+=Math.min(b,T);// 每个电池最多贡献T分钟if(total>=n*T)returntrue;// 提前终止，节省时间}returntotal>=n*T;}}4. 代码优化说明
优化版将验证逻辑内联到二分循环中，减少函数调用开销（仅逻辑合并，核心思路不变）：
classSolution{publiclongmaxRunTime(intn,int[]batteries){longsum=0;for(intcap:batteries){sum+=cap;}longleft=0,right=sum/n,ans=0;while(left<=right){longmid=left+(right-left)/2;// 避免left+right溢出longtotal=0;for(intcap:batteries){total+=Math.min(cap,mid);}if(total>=n*mid){ans=mid;left=mid+1;}else{right=mid-1;}}returnans;}}5. 复杂度分析
时间复杂度：(O(m \times \log(\text{sum}/n)))
m是电池数量，每次验证需遍历所有电池（(O(m))）；- 二分查找的次数为 (\log(\text{sum}/n))（sum为总电池容量）。
空间复杂度：(O(1))
- 仅使用常量级额外空间。
6. 总结
- 核心思路是二分查找 + 贪心验证：通过二分缩小运行时间的候选范围，用贪心计算电池有效贡献来验证可行性；
- 关键技巧是利用“每个电池最多贡献
T分钟”的贪心策略，快速判断候选时间是否可行； - 该方法高效解决了“最大化同时运行时间”的问题，避免了暴力枚举的高时间复杂度。
