[LeetCode] 875 - Koko Eating Bananas

Problem

给定一个有 n 堆香蕉的阵列 piles (第 i 堆的数量为 piles[i])，以及限时 h 小时，需要找出最少每小时需要吃的香蕉数量，才能在时限内把所有的香蕉吃完。

P.S. 每小时只能吃同一堆香蕉，因此就算那一堆剩余的香蕉数量小于每小时吃的量，也无法跨堆去吃。

Example 1:

Input: piles = [3,6,7,11], h = 8Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6Output: 23

Solution

由于 piles 可能的组合太多，而且无法跨堆吃香蕉。因此，我们只能用穷举的方式来找出答案，但要如何有效率的穷举，是本题最大的考验。

简单整理关于穷举的资讯：

穷举的範围是在 [1, max(piles)] (因为题目保证 piles.length() <= h)假设每小时最少要吃的香蕉树为 k，则 [1, k-1] 的数量都无法在时间内吃完全部香蕉，而 [k, max(piles)] 的数量都可以

有了範围后，我们就不再是盲目地穷举，而是搜寻。那讲到搜寻，最常见有效、且容易实作的方法就是二分搜寻法 (binary search)。

一般的二分搜寻法，是根据数字大于或小于目标，来调整左界或右界。在此题中，我们则要根据每小时吃的香蕉数量 t，是否能在时限内吃完做调整：

可以吃完 → 调整右界为 t (不是 t-1 的原因：不能保证每小时吃 t-1 个也能在时限内吃完，所以只能将右界缩减成确认过的 t 数量)无法吃完 → 调整左界为 t+1

判断能否在时限内吃完，只需把每堆香蕉的数量 / t (记得要无条件进位喔)，计算所需的小时数，再全部加起来。如果总时数符合时限内，则表示可以吃完。

整数除法 (无条件进位) 比较快速的方法

q = (x + y - 1) / y;q = 1 + ((x - 1) / y); // if x != 0

Complexity

n 为 piles size

Time complexity: O(nlogn)

Binary search 总共会搜寻 logn 个数字 * 每个数字的检查需要扫过整个 array O(n) → O(nlongn)

Space complexity: O(1)

Code

class Solution {public:    bool valid(vector<int> &piles, int h, int k) {        int hr = 0;        for (int p : piles) hr += (p + k - 1) / k;        return hr <= h;    }    int minEatingSpeed(vector<int>& piles, int h) {        int l = 1, r = 0;        for (int p : piles) r = max(p, r);        while (l < r) {            int m = (l + r) / 2;            if (valid(piles, h, m)) r = m;            else l = m + 1;        }        return r;    }};

LeetCode Link

https://leetcode.com/problems/koko-eating-bananas/