LeetCode875 - (medium) Koko Eating Bananas
文章目录
Task
Koko loves to eat bananas. There are N
piles of bananas, the i
-th pile has piles[i]
bananas. The guards have gone and will come back in H
hours.
Koko can decide her bananas-per-hour eating speed of K
. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K
bananas, she eats all of them instead, and won’t eat any more bananas during this hour.
Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer K
such that she can eat all the bananas within H
hours.
Example
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Constraints:
1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9
Solution
- 取数组中的最大元素,按照此速度吃一定能吃完。在0和该速度之间搜索出一个能吃完的最小速度,用二分搜索
- 每次取一个中点时,都计算以该速度吃完所需的时间,以此来判断下次搜索的区间
时间复杂度
:每一次二分时都需遍历整个数组来计算时间O(n),而二分次数取决于数组中最大元素m,故总时间复杂度O(nlogm)空间复杂度
:O(1)- 实现:
|
|