珂珂喜欢吃香蕉。这里有 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^4piles.length <= H <= 10^91 <= piles[i] <= 10^9来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/koko-eating-bananas著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的回答
解法一
时间复杂度 O(m*n) 两个循环 n 为数组长度，m 为 k—次数
空间复杂度 O(1) 创建了 2 个新的空间
暴力法超时了
var minEatingSpeed = function(piles, H) { let k = Math.max(...piles); while (true) { let count = 0; for (let i = 0; i < piles.length; i++) { count += Math.ceil(piles[i] / k); } if (count > H) return k + 1; k--; }};
解法二
时间复杂度 O(m*logn) m 为数组长度，logn 是二分次数
空间复杂度 O(1) 创建了 2 个新的空间
第一次超时了，然后实际上 k 是一个 0-max（…piles)的有序数组，查找其中合适的一个值，那么就可以使用二分法
function isEatAll(piles, H, k) { let count = 0; for (let i = 0; i < piles.length; i++) { count += Math.ceil(piles[i] / k); } return count > H;}var minEatingSpeed = function(piles, H) { let right = Math.max(...piles); let left = 0; while (left <= right) { let mid = ~~((left + right) / 2); if (isEatAll(piles, H, mid)) { left = mid + 1; } else { right = mid - 1; } } return left;};
class Solution: def canEatAllBananas(self, piles, H, K): t = 0 for pile in piles: t += math.ceil(pile / K) return t <= H def minEatingSpeed(self, piles: List[int], H: int) -> int: l, r = 1, max(piles) # [l, r) ， 左闭右开的好处是如果能找到，那么返回 l 和 r 都是一样的，因为最终 l 等于 r。 while l < r: mid = (l + r) >> 1 if self.canEatAllBananas(piles, H, mid): r = mid else: l = mid + 1 return l
JavaScript Code:
function canEatAllBananas(piles, H, mid) { let h = 0; for (let pile of piles) { h += Math.ceil(pile / mid); } return h <= H;}/** * @param {number[]} piles * @param {number} H * @return {number} */var minEatingSpeed = function(piles, H) { let lo = 1, hi = Math.max(...piles); // [l, r) ， 左闭右开的好处是如果能找到，那么返回 l 和 r 都是一样的，因为最终 l 等于 r。 while (lo <= hi) { let mid = lo + ((hi - lo) >> 1); if (canEatAllBananas(piles, H, mid)) { hi = mid - 1; } else { lo = mid + 1; } } return lo; // 不能选择hi};
复杂度分析
时间复杂度：O(max(N,N∗logM))，其中 N 为 piles 长度， M 为 Piles 中最大的数。
空间复杂度：O(1)
模板
分享几个常用的的二分法模板。
查找一个数
public int binarySearch(int[] nums, int target) { // 左右都闭合的区间 [l, r] int left = 0; int right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; else if (nums[mid] < target) // 搜索区间变为 [mid+1, right] left = mid + 1; else if (nums[mid] > target) // 搜索区间变为 [left, mid - 1] right = mid - 1; } return -1;}
寻找最左边的满足条件的值
public int binarySearchLeft(int[] nums, int target) { // 搜索区间为 [left, right] int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索区间变为 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收缩右边界 right = mid - 1; } } // 检查是否越界 if (left >= nums.length || nums[left] != target) return -1; return left;}
寻找最右边的满足条件的值
public int binarySearchRight(int[] nums, int target) { // 搜索区间为 [left, right] int left = 0 int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索区间变为 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收缩左边界 left = mid + 1; } } // 检查是否越界 if (right < 0 || nums[right] != target) return -1; return right;}
