leetcode
leetcode 751 ~ 800
爱吃香蕉的珂珂

爱吃香蕉的珂珂

难度:

标签:

题目描述

代码结果

运行时间: 41 ms, 内存: 17.1 MB


// 思路:
// 1. 使用二分查找法找出最小速度 k。
// 2. 使用 Java Stream API 获取香蕉堆的最大值。
// 3. 计算中间速度,并验证在该速度下是否能在 h 小时内吃完所有香蕉。
// 4. 如果能在 h 小时内吃完,则将右边界调整为中间速度;否则,将左边界调整为中间速度 + 1。

import java.util.Arrays;

public class KokoEatingBananasStream {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = Arrays.stream(piles).max().getAsInt();
        while (left < right) {
            int mid = (left + right) / 2;
            if (canFinish(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canFinish(int[] piles, int h, int k) {
        return Arrays.stream(piles).map(pile -> (pile + k - 1) / k).sum() <= h;
    }
}

解释

方法:

此题的解决方法是采用二分查找来找到珂珂可以在 h 小时内吃完所有香蕉的最小速度 k。这里定义了一个 check 函数来判断给定速度 x 下珂珂能否在 h 小时内吃完所有的香蕉。check 函数通过遍历所有香蕉堆,计算在速度 x 下需要的总时间。如果这个总时间小于等于 h,说明这个速度可行。通过不断调整速度的搜索范围(即二分查找的上下界),最终找到可以满足条件的最小速度。二分查找的初始左界 l 和右界 r 的设定基于总香蕉数和堆数的关系,以缩小搜索范围,提高效率。

时间复杂度:

O(n log m)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,如何确定二分查找的初始上界和下界?具体是基于什么考虑?
在这个算法中,二分查找的初始上界和下界是基于香蕉总数和时间限制来设定的。下界l为香蕉总数除以时间加上堆数后再加1,目的是确保即使分配最不利,也有足够的速度去吃完所有香蕉。上界r则是香蕉总数除以时间减去堆数后再加1,这是考虑到最快的速度场景。这样做是为了确保搜索范围既包含可能的最小速度,也不过分宽泛以致效率低下。
🦆
为什么在计算速度时使用的是`sums // (h + n) + 1`和`sums // (h - n) + 1`而不是其他表达式?
这里的表达式`sums // (h + n) + 1`和`sums // (h - n) + 1`用于估计可能的最小和最大速度。`sums // (h + n) + 1`作为下界考虑了即使在最慢的情况下也应该有足够的速度完成任务,而`sums // (h - n) + 1`作为上界则考虑到最快情况的可能性。这两个表达式提供了一个合理的速度范围,使得二分查找能更高效地找到解。
🦆
在实际计算中,如果h的值非常接近n(堆数),算法的表现如何?是否存在特殊情况需要额外注意?
如果h的值非常接近n,情况特殊因为每堆香蕉至少需要一小时来处理,这意味着珂珂的吃香蕉速度至少得是每堆中的最大数量。在这种情况下,若h等于n,算法直接返回最大堆的大小作为最小速度,因为没有其他速度可以在每堆只能分配一小时的情况下完成任务。这是一种边界情况,需要特别处理以确保算法的正确性和效率。
🦆
给定的二分查找算法中,退出循环时返回的是l,这是否总是保证l是满足条件的最小速度?为什么?
是的,退出循环时返回的l总是满足条件的最小速度。在二分查找中,当检测到某个速度mid能让珂珂在规定时间内吃完所有的香蕉时,我们将上界r调整为mid-1,继续寻找是否有更小的可行速度。如果某个速度不可行,就调整下界l为mid+1。最终,当l超过r时,l即为满足条件的最小速度。这是因为最后一次使check函数返回true的mid,其值即为l-1,而l是第一个使check函数返回false的值,因此l是满足条件的最小速度。

相关问题

最小化去加油站的最大距离

最小化去加油站的最大距离