day121—二分查找—爱吃香蕉的珂珂（LeetCode-875）

题目描述

珂珂喜欢吃香蕉。这里有n堆香蕉，第i堆中有piles[i]根香蕉。警卫已经离开了，将在h小时后回来。

珂珂可以决定她吃香蕉的速度k（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉k根。如果这堆香蕉少于k根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在h小时内吃掉所有香蕉的最小速度k（k为整数）。

示例 1：

输入：piles = [3,6,7,11], h = 8输出：4

示例 2：

输入：piles = [30,11,23,4,20], h = 5输出：30

示例 3：

输入：piles = [30,11,23,4,20], h = 6输出：23

提示：

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

解决方案：

算法目标

找出Koko每小时吃香蕉的最小速度k，使得她能在h小时内吃完所有香蕉堆。

核心思路

1. 确定查找范围：速度k在[1, 最大香蕉堆]之间

2. 二分查找：尝试不同的速度，找到满足条件的最小速度

3. 验证可行性：对每个尝试的速度，计算吃完所有香蕉需要的时间

算法步骤

1. 确定二分查找范围

int max_p = 0; for(auto p : piles) { max_p = max(max_p, p); } int left = 0; // 不可行的下界 int right = max_p + 1; // 可行的上界（开区间）

• 最小速度：1（每小时至少吃1根）

• 最大速度：最大香蕉堆的大小（一次吃完一堆）

• 使用开区间(left, right)，left永远不可行，right永远可行

2. 二分查找主循环

while(left + 1 < right) { int mid = left + (right - left) / 2; // 尝试的速度 // 计算以速度mid需要的时间 // 判断并更新边界 }

3. 计算所需时间

int tmp_hour = 0; for(auto p : piles) { tmp_hour += (p + mid - 1) / mid; // 向上取整 if(tmp_hour > h) break; // 提前退出优化 }

• 对每堆香蕉p，计算需要的小时数：ceil(p / mid)

• 使用整数向上取整技巧：(p + mid - 1) / mid

• 累加总时间

• 提前退出：如果已超过h小时，立即停止计算

4. 判断并更新边界

if(tmp_hour > h) { left = mid; // 速度太慢，不可行 } else { right = mid; // 速度可行，尝试更小的 }

5. 返回结果

return right; // 最小的可行速度

关键点

• 二分查找对象：吃香蕉的速度k，不是数组索引

• 验证条件：以速度k吃完所有香蕉的时间≤ h

• 搜索方向：寻找满足条件的最小k

• 边界处理：使用开区间确保正确性

时间复杂度

• 寻找最大值：O(n)

• 二分查找：O(log M)，M为最大香蕉堆大小

• 每次验证：O(n)

• 总时间：O(n log M)

示例

piles = [3,6,7,11] h = 8 查找过程： 1. 范围: k ∈ [1, 11] 2. 尝试 k=6: 需要6小时 ≤ 8 → 可行 3. 尝试 k=3: 需要10小时 > 8 → 不可行 4. 尝试 k=4: 需要8小时 ≤ 8 → 可行 5. 尝试 k=5: 需要8小时 ≤ 8 → 可行 6. 最终结果: k=4

函数源码：

class Solution { public: int minEatingSpeed(vector<int>& piles, int h) { int max_p=0; for(auto p:piles){ max_p=max(max_p,p); } int left=0; int right=max_p+1; while(left+1<right){ int mid=(right+left)/2; int tmp_hour=0; for(auto p:piles){ tmp_hour+=(p+mid-1)/mid; if(tmp_hour>h) break; } if(tmp_hour>h) left=mid; else right=mid; } return right; } };