【二分查找】875. 爱吃香蕉的珂珂

2024-02-26 20:12

文章标签 二分查找香蕉 875

本文主要是介绍【二分查找】875. 爱吃香蕉的珂珂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

875. 爱吃香蕉的珂珂

解题思路

minEatingSpeed 方法是解决问题的入口。它接收一个整数数组 piles（每堆香蕉的数量）和一个整数 h（在规定时间内需要吃完所有香蕉的小时数）。该方法通过二分搜索来确定最小的吃香蕉速度，使得在规定时间内能够吃完所有香蕉。
left 和 right 变量用于指示当前二分搜索的左右边界。left 初始化为 1，而 right 初始化为 piles 数组中最大堆的香蕉数量加一。
使用 while 循环进行二分搜索。循环条件是 left 小于等于 right。
在循环中，通过求取中间值 mid，即 (right - left) / 2 + left。这是典型的二分搜索方法。
然后调用 canFinish 方法，判断是否能够在规定时间内以当前速度吃完所有香蕉。如果可以，说明当前速度可能偏大，因此将 right 更新为 mid - 1，即向左移动右边界，缩小搜索范围。
如果不能在规定时间内吃完所有香蕉，则说明当前速度太小，需要增大速度。因此将 left 更新为 mid + 1，即向右移动左边界，继续搜索。
最终返回 left，它表示在规定时间内能够吃完所有香蕉的最小速度。
canFinish 方法用于判断以指定速度是否能在规定时间内吃完所有香蕉。它遍历每一堆香蕉，计算吃完每堆香蕉所需的时间总和，并与规定时间 H 进行比较。如果总时间小于等于规定时间，则返回 true，否则返回 false。
timeOf 方法用于计算吃完一堆香蕉所需的时间。它接收两个参数，一个是堆的香蕉数量 n，另一个是吃香蕉的速度 speed。返回值是吃完这堆香蕉所需的时间，向上取整。
getMax 方法用于获取数组中的最大值，并将其返回。

class Solution {public int minEatingSpeed(int[] piles, int h) {// 二分搜索的左侧边界int left = 1;int right =  getMax(piles) + 1;while(left <= right){int mid = (right - left)  / 2 + left;if(canFinish(piles,mid,h)){// 计算能不能完成right = mid - 1;//缩小右边界 }else{left = mid + 1;// 不能完成 缩小左边界}}return left;}// 判断能不能吃完boolean canFinish(int[] piles,int speed,int H){long time = 0;for(int n:piles){time += timeOf(n,speed);}return time <= H;// 指定时间能不能完成}// 计算每一堆香蕉 需要吃多久 吃不完按照一小时计算 吃得完 下一小时继续 两小时long timeOf(int n,int speed){return (n / speed) + ((n % speed > 0) ? 1:0);}// 找出最大值int getMax(int[] piles){int max = 0;for(int n:piles){max = Math.max(n,max);}return max;}
}