题目

爱吃香蕉的珂珂

解题思路

要求返回在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数），转化一下等同于求右区间的左边界。

一般二分搜索都需要一个有序数列，此题没有有序数列，那怎么办呢？
观察可知，如果有一个函数$f(k)$来表示当吃香蕉速度为$k$时，吃完所有香蕉所用的时间，那么$f(k)$是随着$k$单调递减的。
只有知道了单调性，我们才能通过大小比较，来进行搜索区间的缩小。

代码实现

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:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        
        # 判断当前速度k，能否在h小时内吃完
        def _can_finish(x):
            cnt = 0
            for p in piles:
                cnt += p // x 
                if p % x:
                    cnt += 1
            return cnt <= h

        left = 1
        right = max(piles)
        while left <= right:
            mid = left + (right - left) // 2
            # 如果能吃完，需要看更小的速度能不能吃完，则目标值在mid左侧，right左移
            if _can_finish(mid):  
                right = mid - 1
            # 如果不能吃完，需要看更大的速度能否吃完，则目标值在mid右侧，left右移
            else:  
                left = mid + 1
        # 想想，为什么最后是返回left？
        return left