Medium

题目描述

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

解题思路

这是一道经典的二分查找题目，核心思路是在可能的速度范围内进行二分搜索。

问题分析： 我们需要找到最小的吃香蕉速度 k，使得珂珂能在 h 小时内吃完所有香蕉。对于给定的速度 k，我们可以计算出吃完所有香蕉所需的时间。

解法思路：

  1. 确定搜索范围：速度 k 的最小值为 1，最大值为 max(piles)（最大堆的香蕉数）
  2. 二分查找：在 [1, max(piles)] 范围内进行二分搜索
  3. 验证函数：对于给定速度 k，计算吃完所有香蕉需要的时间
    • 对于每堆 piles[i]，需要 ⌈piles[i]/k⌉ 小时（向上取整）
    • 总时间为所有堆所需时间的和
  4. 二分逻辑：
    • 如果当前速度能在 h 小时内吃完，说明答案可能更小，在左半部分继续搜索
    • 如果当前速度不能在 h 小时内吃完，需要更大的速度，在右半部分搜索

时间复杂度优化： 向上取整可以用 (piles[i] + k - 1) / k 来避免浮点运算。

代码实现

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1, right = *max_element(piles.begin(), piles.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
private:
    bool canFinish(vector<int>& piles, int h, int k) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile + k - 1) / k;  // 向上取整
        }
        return hours <= h;
    }
};

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def can_finish(k):
            hours = 0
            for pile in piles:
                hours += (pile + k - 1) // k  # 向上取整
            return hours <= h
        
        left, right = 1, max(piles)
        
        while left < right:
            mid = (left + right) // 2
            if can_finish(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        int left = 1, right = piles.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CanFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private bool CanFinish(int[] piles, int h, int k) {
        int hours = 0;
        foreach (int pile in piles) {
            hours += (pile + k - 1) / k;  // 向上取整
        }
        return hours <= h;
    }
}

var minEatingSpeed = function(piles, h) {
    const canFinish = (k) => {
        let hours = 0;
        for (let pile of piles) {
            hours += Math.ceil(pile / k);
        }
        return hours <= h;
    };
    
    let left = 1, right = Math.max(...piles);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canFinish(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log(max(piles)))二分查找范围为 [1, max(piles)]，每次验证需要 O(n) 时间
空间复杂度O(1)只使用了常数级别的额外空间

相关题目