爱吃香蕉的珂珂

怎样从“piles=[3,6,7,11],h=8,最小速度 k 使 h 小时内吃完。”推导出 二分答案 · 吃香蕉，并证明每次状态变化都不会漏掉答案？

中心结论：二分 k,验证 sum(ceil(p/k))<=h。

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

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

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

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

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

在本站主例中，piles=[3,6,7,11],h=8,最小速度 k 使 h 小时内吃完。

算法最终需要得到或观察：最小 k=4。

枚举每一个可能答案会做大量相似验证；可行性单调时，可以直接在答案空间二分。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“答案可行性刻度”，明确答案需要观察什么。
2. 2状态只维护 lo/hi 速度、验证和。
3. 3转移每一步按照 二分 k,验证 sum(ceil(p/k))<=h。
4. 4收尾读取 最小 k=4。，并复核边界与复杂度。

先证明答案越大或越小时，可行性只朝一个方向变化。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：lo/hi 速度、验证和。

给出一个数组，数组里面每个元素代表的是每个香蕉🍌串上香蕉的个数。koko 以 `k 个香蕉/小时`的速度吃这些香蕉。守卫会在 `H 小时`以后回来。问 k 至少为多少，能在守卫回来之前吃完所有的香蕉。当香蕉的个数小于 k 的时候，这个小时只能吃完这些香蕉，不能再吃其他串上的香蕉了。 这一题可以用二分搜索来解答。在 `[0 , max(piles)]` 的范围内搜索，二分的过程都是常规思路。判断是否左右边界如果划分的时候需要注意题目中给的限定条件。当香蕉个数小于 k 的时候，那个小时不能再吃其他香蕉了。

二分 k,验证 sum(ceil(p/k))<=h。

执行过程中持续维护：lo/hi 速度、验证和。

正确性依赖以下不变量：验证随 k 增大单调更易完成。

面试时可以压缩为：二分答案+验证 O(n log maxP)。

落到当前题，执行机制可以压缩为：二分 k,验证 sum(ceil(p/k))<=h。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入piles=[3,6,7,11],h=8,最小速度 k 使 h 小时内吃完。 因为：二分 k,验证 sum(ceil(p/k))<=h。
2. 2二分最慢速度 speed单调可行函数。 因为：最小可行 speed 即答案。
3. 3speed=6 需 6 小时 ≤ 8模拟吃香蕉小时数。 因为：ceil(p/speed) 累加。
4. 4speed=3 需 10 小时 > 8模拟吃香蕉小时数。 因为：ceil(p/speed) 累加。
5. 5speed=5 需 8 小时 ≤ 8模拟吃香蕉小时数。 因为：ceil(p/speed) 累加。
6. 6speed=4 需 8 小时 ≤ 8模拟吃香蕉小时数。 因为：ceil(p/speed) 累加。
7. 7最慢速度 = 4返回最小可行速度。 因为：O(n log max pile)。
8. 8收尾与复杂度最小 k=4。 因为：时间 O(n) · 空间 O(1)。二分 k,验证 sum(ceil(p/k))<=h。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "math"

func minEatingSpeed(piles []int, H int) int {
	low, high := 1, maxInArr(piles)
	for low < high {
		mid := low + (high-low)>>1
		if !isPossible(piles, mid, H) {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return low
}

func isPossible(piles []int, h, H int) bool {
	res := 0
	for _, p := range piles {
		res += int(math.Ceil(float64(p) / float64(h)))
	}
	return res <= H
}

func maxInArr(xs []int) int {
	res := 0
	for _, x := range xs {
		if res < x {
			res = x
		}
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="koko-bananas", piles=[3,6,7,11], h=8
    //    期望：最小 k=4。
    //
    // 2. 失败 / 未命中
    //    检查：ceil 除法用 (p+k-1)/k。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC410 分割；LC1011 船运
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意piles=[3,6,7,11],h=8,最小速度 k 使 h 小时内吃完。
2. 2重复枚举每一个可能答案会做大量相似验证；可行性单调时，可以直接在答案空间二分。
3. 3优化二分 k,验证 sum(ceil(p/k))<=h。
4. 4证明验证随 k 增大单调更易完成。
5. 5复杂度时间 O(n)，空间 O(1)