How does binary search help in the Koko Eating Bananas problem?

Binary search efficiently narrows down the minimum speed by testing feasible speeds and narrowing the range based on the result of each test.

What is the time complexity of the Koko Eating Bananas problem?

The time complexity is O(n log(max(piles))), where n is the number of piles and max(piles) is the largest pile size.

What is the correct way to implement the time calculation for each candidate speed?

For each pile, calculate how many hours it takes to finish eating with the current speed, summing these hours across all piles.

What should I do if the solution takes too long for large inputs?

Ensure that the binary search space is set up correctly and consider optimizing the implementation of the feasibility check.

How does GhostInterview assist in solving this problem?

GhostInterview helps by guiding through binary search applications, highlighting common mistakes, and providing tailored practice for interview success.

#875

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉…

数组二分查找

题目描述

珂珂喜欢吃香蕉。这里有 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⁹

lightbulb

解题思路

方法一：二分查找

我们注意到，如果珂珂能够以 $k$ 的速度在 $h$ 小时内吃完所有香蕉，那么她也可以以 $k' > k$ 的速度在 $h$ 小时内吃完所有香蕉。这存在着单调性，因此我们可以使用二分查找，找到最小的满足条件的 $k$ 。

我们定义二分查找的左边界 $l = 1$ ，右边界 $r = \max(\textit{piles})$ 。每一次二分，我们取中间值 $mid = \frac{l + r}{2}$ ，然后计算以 $mid$ 的速度吃香蕉需要的时间 $s$ 。如果 $s \leq h$ ，说明 $mid$ 的速度可以满足条件，我们将右边界 $r$ 更新为 $mid$ ；否则，我们将左边界 $l$ 更新为 $mid + 1$ 。最终，当 $l = r$ 时，我们找到了最小的满足条件的 $k$ 。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组 $\textit{piles}$ 的长度和最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def check(k: int) -> bool:
            return sum((x + k - 1) // k for x in piles) <= h

        return 1 + bisect_left(range(1, max(piles) + 1), True, key=check)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of binary search by efficiently narrowing down the valid range of speeds.
question_mark
The candidate accurately implements a feasibility check for each candidate speed, ensuring that Koko finishes in time.
question_mark
The candidate handles edge cases well, ensuring the solution works even for the largest inputs.

warning

常见陷阱

外企场景

error
Misunderstanding the binary search space: candidates may mistakenly define the range of speeds incorrectly, such as starting with the wrong lower or upper bound.
error
Incorrectly implementing the time calculation: the candidate may fail to correctly calculate how many hours Koko needs for each pile.
error
Not handling large input sizes efficiently: candidates may overlook the performance of their solution, resulting in an inefficient or slow approach.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem by changing the number of piles or the time limit to test the efficiency of the solution.
arrow_right_alt
Consider variations where Koko can eat from multiple piles simultaneously, changing the problem’s complexity.
arrow_right_alt
Increase the number of piles significantly to test how the binary search approach scales.

help

常见问题

外企场景

继续练习

#862 和至少为 K 的最短子数组 #888 公平的糖果交换 #852 山脉数组的峰顶索引