算法题 爱吃香蕉的珂珂

爱吃香蕉的珂珂

问题描述

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

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

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

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

示例：

输入:piles=[3,6,7,11],h=8输出:4解释:-速度为4时：[1,2,2,3]=8小时-速度为3时：[1,2,3,4]=10小时 输入:piles=[30,11,23,4,20],h=5输出:30解释:每堆需要1小时，总共5小时 输入:piles=[30,11,23,4,20],h=6输出:23

算法思路

二分搜索：

1. 搜索范围：

   • 最小速度：1（每小时至少吃1根）
   • 最大速度：max(piles)（每堆最多需要1小时）
   • 速度k的范围是[1, max(piles)]

2. 单调性：

   • 如果速度k能在h小时内吃完，那么任何速度> k也一定能吃完
   • 如果速度k不能在h小时内吃完，那么任何速度< k也一定不能吃完

3. 时间计算：

   • 对于速度k，吃掉第i堆香蕉需要的时间为：ceil(piles[i] / k)
   • 总时间 =sum(ceil(piles[i] / k)) for all i
   • ceil(a/b)可以用(a + b - 1) / b计算（整数除法）

4. 搜索策略：

   • 寻找满足条件的最小k
   • 如果time(k) <= h，说明k可行，尝试更小的速度（right = k）
   • 如果time(k) > h，说明k太小，需要更大的速度（left = k + 1）

代码实现

方法一：二分搜索

classSolution{/** * 找到珂珂吃香蕉的最小速度 * * @param piles 香蕉堆数组 * @param h 警卫离开的小时数 * @return 最小速度k * * 算法思路： * 1. 确定搜索范围：[1, max(piles)] * 2. 使用二分搜索找到满足条件的最小k * 3. 对于每个k，计算总耗时 * 4. 根据耗时与h的比较调整搜索范围 */publicintminEatingSpeed(int[]piles,inth){// 找到最大的香蕉堆数量，作为搜索上界intmaxPile=0;for(intpile:piles){maxPile=Math.max(maxPile,pile);}// 二分搜索范围：[1, maxPile]intleft=1;intright=maxPile;// 二分搜索寻找最小速度while(left<right){intmid=left+(right-left)/2;// 计算以速度mid吃掉所有香蕉需要的总时间longtotalTime=calculateTime(piles,mid);if(totalTime<=h){// 当前速度可行，尝试更小的速度right=mid;}else{// 当前速度太慢，需要更大的速度left=mid+1;}}returnleft;}/** * 计算以给定速度吃掉所有香蕉需要的总时间 * * @param piles 香蕉堆数组 * @param speed 吃香蕉的速度（根/小时） * @return 总时间（小时） * * 使用long防止整数溢出 */privatelongcalculateTime(int[]piles,intspeed){longtotalTime=0;for(intpile:piles){// 计算吃掉当前堆需要的时间：ceil(pile / speed)// ceil(a/b) = (a + b - 1) / btotalTime+=(pile+(long)speed-1)/speed;}returntotalTime;}}

算法分析

• 时间复杂度：O(n log m)

  • n 是香蕉堆的数量
  • m 是最大香蕉堆的数量（搜索空间大小）
  • 二分搜索需要 O(log m) 次迭代
  • 每次迭代需要 O(n) 时间计算总耗时

• 空间复杂度：O(1)

  • 只使用常数额外空间

算法过程

1：piles = [3,6,7,11], h = 8

搜索范围：[1, 11]

二分搜索过程：

left=1, right=11, mid=6 - time(6) = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8 - right = 6 left=1, right=6, mid=3 - time(3) = ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 > 8 - left = 4 left=4, right=6, mid=5 - time(5) = ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5) = 1+2+2+3 = 8 <= 8 - right = 5 left=4, right=5, mid=4 - time(4) = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8 - right = 4 left=4, right=4，循环结束 返回 4

测试用例

importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]piles1={3,6,7,11};inth1=8;System.out.println("Test 1: "+solution.minEatingSpeed(piles1,h1));// 4// 测试用例2：h等于堆数int[]piles2={30,11,23,4,20};inth2=5;System.out.println("Test 2: "+solution.minEatingSpeed(piles2,h2));// 30// 测试用例3：h比堆数多1int[]piles3={30,11,23,4,20};inth3=6;System.out.println("Test 3: "+solution.minEatingSpeed(piles3,h3));// 23// 测试用例4：单堆香蕉int[]piles4={312884470};inth4=312884469;System.out.println("Test 4: "+solution.minEatingSpeed(piles4,h4));// 2// 测试用例5：所有堆都是1int[]piles5={1,1,1,1,1};inth5=5;System.out.println("Test 5: "+solution.minEatingSpeed(piles5,h5));// 1// 测试用例6：h很大int[]piles6={31,26,33,21,40};inth6=100;System.out.println("Test 6: "+solution.minEatingSpeed(piles6,h6));// 1// 测试用例7：边界情况 - h等于总香蕉数int[]piles7={1,2,3,4,5};inth7=15;// 总香蕉数System.out.println("Test 7: "+solution.minEatingSpeed(piles7,h7));// 1// 测试用例8：大数值测试int[]piles8={1000000000};inth8=2;System.out.println("Test 8: "+solution.minEatingSpeed(piles8,h8));// 500000000// 测试用例9：h刚好等于最优解所需时间int[]piles9={3,6,7,11};inth9=8;// 刚好是k=4所需时间System.out.println("Test 9: "+solution.minEatingSpeed(piles9,h9));// 4// 测试用例10：需要最大速度int[]piles10={10,20,30};inth10=3;// 每堆1小时System.out.println("Test 10: "+solution.minEatingSpeed(piles10,h10));// 30}}

关键点

1. 二分搜索：

   • 具有单调性：速度越大，所需时间越少
   • 需要找到满足条件的最小值

2. 时间计算：

   • 使用ceil(pile / speed)而不是floor
   • 整数除法中ceil(a/b) = (a + b - 1) / b

3. 边界条件处理：

   • 最小速度为1（不能为0）
   • 最大速度为max(piles)（更大的速度没有意义）

常见问题

1. 为什么最大速度是 max(piles)？

   • 如果速度 >= max(piles)，每堆最多需要1小时
   • 更大的速度不会减少总时间（因为每堆至少需要1小时）

2. 为什么不用线性搜索？

   • 线性搜索时间复杂度 O(n × m)，可能超时
   • 二分搜索将时间复杂度优化到 O(n log m)