LeetCode LCR 073. 爱吃香蕉的狒狒

Categories:

题目描述
思路分析
1. 解法一：二分答案（推荐）
相似题目

题目描述

✅ LCR 073. 爱吃香蕉的狒狒

思路分析

解法一：二分答案（推荐）

核心思路：

吃香蕉速度越大，总耗时越小，具有单调性。

在 [1, max(piles)] 上二分速度 k。

计算给定速度下的总耗时，若不超过 h 则向左收缩，否则向右收缩。

复杂度分析：

时间复杂度：O(n log M)，其中 n 为堆数，M 为最大堆大小。

空间复杂度：O(1)。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1;
        for (int p : piles) {
            right = Math.max(right, p);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canFinish(int[] piles, int h, int speed) {
        long hours = 0;
        for (int p : piles) {
            hours += (p + speed - 1) / speed;
            if (hours > h) {
                return false;
            }
        }
        return true;
    }
}

func minEatingSpeed(piles []int, h int) int {
    left, right := 1, 1
    for _, p := range piles {
        if p > right {
            right = p
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canFinish(piles, h, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

func canFinish(piles []int, h int, speed int) bool {
    hours := 0
    for _, p := range piles {
        hours += (p + speed - 1) / speed
        if hours > h {
            return false
        }
    }
    return true
}

相似题目

题目	难度	考察点
410. 分割数组的最大值	困难	二分答案
1011. 在 D 天内送达包裹的能力	中等	二分答案
1283. 使结果不超过阈值的最小除数	中等	二分
1482. 制作 m 束花所需的最少天数	中等	二分答案
1552. 两球之间的磁力	中等	二分答案

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/38436010