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 <= 10⁴
• piles.length <= h <= 10⁹
• 1 <= piles[i] <= 10⁹

题解

本题本质是使用二分查找寻找左边界问题。
在[1, MAX_PILE]中寻找最小能满足在 h 小时内吃掉所有香蕉的值。
最慢速度为每小时吃一根香蕉，最快为每小时吃max(piles)根香蕉，然后我们尝试某个中点速度k：
(1) 如果以这个速度能够在h小时内吃完香蕉就记录一下这个速度，然后往这个速度的左边查找（看能不能再慢一点）；
(2) 否则就到这个速度的右边查找，看再快点能不能在h小时内吃完香蕉。

注意事项：
假设吃香蕉的速度是 speed，则当一堆香蕉的个数是 pile 时，吃掉这堆香蕉需要 $\lceil \frac{pile}{speed} \rceil$小时，由此可以计算出吃掉所有香蕉需要的时间。如果在速度 speed 下可以在 h 小时内吃掉所有的香蕉，则最小速度一定小于或者等于 speed，因此将上界调整为 speed；否则，最小速度一定大于 speed，因此将下界调整为 speed+1。
实现方面有个小技巧，在计算吃掉每一堆香蕉的时间时，由于 pile 和 speed 都大于0，因此向上取整 $\lceil \frac{pile}{speed} \rceil$ 等价于向下取整 $\lfloor \frac{pile+speed-1}{speed} \rfloor$

代码实现

func minEatingSpeed(piles []int, h int) int {
	low, high := 1, 0
	for _, pile := range piles {
		if pile > high {
			high = pile
		}
	}
	k := high
	for low < high {
		speed := low + (high-low)/2
		delta := getTime(piles, speed)
		if delta > h {
			// mid偏小，搜索区间变为 [mid+1, right]
			low = speed + 1
		} else if delta <= h {
			k = speed
			// mid偏大，搜索区间变为 [left, mid]
			high = speed
		}
	}
	return k
}

func getTime(piles []int, speed int) int {
	time := 0
	for _, p := range piles {
		// 如果一小时能吃掉一堆，则delta + 1
		if speed > p {
			time++
			continue
		}
		// 如果一小时吃不掉一堆，则计算需要花费几小时
		time += p / speed
		if r := p % speed; r != 0 {
			time++
		}
	}
	return time
}