[LeetCode]Koko Eating Bananas

这道题第一反应就是值域上的binary search，因为对于给定的k(每小时吃k个)，很容易在O(N)的时间里验证H小时内是否可以吃完所有的香蕉，N为输入数组的长度。时间复杂度O(N * log M)，M为每个pile的上界，这里是10^9。常数空间，代码如下：

	class Solution {
	public:
	int minEatingSpeed(vector<int>& piles, int H) {
	int len = piles.size(), lo = 1, hi = 1000000000;
	while(lo <= hi)
	{
	int mid = lo + (hi - lo) / 2;
	if(canFinish(piles, mid, H))
	hi = mid - 1;
	else
	lo = mid + 1;
	}
	return lo;
	}
	private:
	bool canFinish(vector<int>& piles, int k, int H)
	{
	int hours = 0, i = 0, len = piles.size();
	while(i < len)
	{
	int h = (piles[i++] - 1) / k + 1;
	hours += h;
	if(hours > H)return false;
	}
	return true;
	}
	};

view raw Koko Eating Bananas.cpp hosted with ❤ by GitHub