描述

狒狒喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

狒狒可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例


示例 1:

  1. 输入: piles = [3,6,7,11], H = 8
  2. 输出: 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^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

解题思路

这是一道典型的二分答案的题。

  • 首先，确定二分答案的边界，答案的最大值应该是数组中的最大值
  • 对于每一个答案，我们需要用一个函数判断是否满足条件
  • 我们的目标是找到满足条件的最小的答案，所以用寻找左边界的二分法

代码

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int max = 0;
        for (int x : piles) {
            max = Math.max(max, x);
        }
        int left = 1, right = max + 1;
        while (left < right) { // 找左边界的二分
            int mid = (left + right)/2;
            if (check(mid, piles, h)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    public boolean check(int K, int[] piles, int h) {
        int time = 0;
        for (int x : piles) {
            time += (x - 1)/K + 1;  // 这个写法可以记一下
        }
        return time <= h ? true : false;
    }
}

复杂度分析：

时间复杂度：O(Nlogmax(piles))，这里 N 表示数组 piles 的长度。我们在 [1,maxpiles] 里使用二分查找定位最小速度，而每一次执行判别函数的时间复杂度是 O(N)；
空间复杂度：O(1)，算法只使用了常数个临时变量。