題目鏈接

愛吃香蕉的珂珂

題目描述

注意點

• piles.length <= h <= 10^9
• 如果某堆香蕉少于k根，將吃掉這堆的所有香蕉，然后這一小時內不會再吃更多的香蕉
• 返回可以在 h 小時內吃掉所有香蕉的最小速度 k（k 為整數）

解答思路

• 二分查找找到在 h 小時內吃掉所有香蕉的最小速度k，已知珂珂保證在h小時內吃完所有香蕉時最快速度max為Math.max(piles)，吃香蕉的最慢速度min為1（但是不保證在h小時內能吃完所有香蕉），min和max就是二分查找的左右邊界，在二分查找時，每次找到左右邊界的中間點mid判斷mid速度能否在h小時內吃完，如果能則max = mid - 1，如果不能則min = mid + 1，找到滿足吃完香蕉的最慢速度即可

代碼

class Solution {public int minEatingSpeed(int[] piles, int h) {int min = 1;int max = 0;for (int pile : piles) {max = Math.max(max, pile);}while (min <= max) {int mid = min + (max - min >> 1);long time = 0;for (int pile : piles) {// 不能整除則向上取整time += (pile + mid - 1) / mid;}if (time > h) {min = mid + 1;} else {max = mid - 1;}}return min;}
}

關鍵點

• 二分查找的思想
• 如果某堆香蕉少于k根，將吃掉這堆的所有香蕉，然后這一小時內不會再吃更多的香蕉
• 找到在h小時內吃完所有香蕉的最慢速度