Task

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example

Example 1:

1
2
Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

1
2
Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

1
2
Input: piles = [30,11,23,4,20], H = 6
Output: 23

Constraints:

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

Solution

  • 取数组中的最大元素,按照此速度吃一定能吃完。在0和该速度之间搜索出一个能吃完的最小速度,用二分搜索
  • 每次取一个中点时,都计算以该速度吃完所需的时间,以此来判断下次搜索的区间
  • 时间复杂度:每一次二分时都需遍历整个数组来计算时间O(n),而二分次数取决于数组中最大元素m,故总时间复杂度O(nlogm)
  • 空间复杂度:O(1)
  • 实现:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Runtime: 96 ms, faster than 63.38% of C++ online submissions for Koko Eating Bananas.
// Memory Usage: 18.8 MB, less than 46.96% of C++ online submissions for Koko Eating Bananas.
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        //使用标准库算法查找最大值
        int max=*max_element(piles.begin(),piles.end());
        int l=1,r=max;
        //二分查找
        while(l<r){
            int m=l+(r-l)/2;
            //计算吃完所有需要的时间
            int t=0;
            for(int p:piles)
                //同时考虑能整除和不能整除的情形,等价于:
                //t+=(p%m==0)?(p/m):(p/m+1);
                t+=(p+m-1)/m;
            if(t>H)
                l=m+1;
            else
                r=m;
        }
        return l;
    }
};