Koko Eating Bananas

875. 爱吃香蕉的珂珂

分析

定义区间：
- 吃香蕉速度的下界 l 为 1（最低速度）
- 吃香蕉速度的上界 r 为 10^9（最大速度，假设所有香蕉都在一堆中且时间充足）
判断函数 getTime(piles, k) ：
- 计算以速度 k 吃完所有香蕉需要的时间
- 遍历每堆香蕉 pile ，需要的时间为 pile / k 上取整，可以通过 (pile + k - 1) / k 实现
二分查找：
- 计算中间值 mid = (l + r) / 2 ：
  - 如果 getTime(piles, mid) <= h ，说明速度 mid 可以满足要求，但可能还有更小的速度满足条件，因此缩小上界 r = mid
  - 如果 getTime(piles, mid)} > h ，说明速度 mid 不够快，需要增大速度，更新下界 l = mid + 1
结束条件：
- 当 l == r 时，搜索范围缩小到单一值，返回 l 或 r 即为最小速度

时间复杂度

二分查找最多进行 O(log(10^9)) 次
每次计算 getTime(piles, k) 需要 O(n)，其中 n 是香蕉堆的数量

总复杂度为 O(n * log(10^9))

空间复杂度

空间复杂度为 O(1)

C++代码

 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
26


class Solution
             {
public:
    // 判断以速度 k 吃完所有香蕉需要的时间
    int getTime(std::vector<int>& piles, int k)
    {
        int res = 0;
        for (int pile : piles)
            res += (pile + k - 1) / k; // 等价于 ceil(pile / k)
        return res;
    }

    int minEatingSpeed(vector<int>& piles, int h)
    {
        int l = 1, r = 1e9; // 定义速度的搜索区间
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (getTime(piles, mid) <= h) // 如果当前速度满足条件
                r = mid; // 尝试更小的速度
            else
                l = mid + 1; // 增大速度
        }
        return r; // 返回最小速度
    }
};