難度：★★★☆☆
類型：數(shù)組
方法：數(shù)學(xué)
力扣鏈接請(qǐng)移步本題傳送門
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄
題目
珂珂喜歡吃香蕉。這里有 N 堆香蕉撑碴，第 i 堆中有 piles[i] 根香蕉妒潭。警衛(wèi)已經(jīng)離開了，將在 H 小時(shí)后回來辣垒。
珂珂可以決定她吃香蕉的速度 K （單位：根/小時(shí)）酥馍。每個(gè)小時(shí)坦喘，她將會(huì)選擇一堆香蕉，從中吃掉 K 根蛋济。如果這堆香蕉少于 K 根棍鳖，她將吃掉這堆的所有香蕉，然后這一小時(shí)內(nèi)不會(huì)再吃更多的香蕉碗旅。
珂珂喜歡慢慢吃渡处，但仍然想在警衛(wèi)回來前吃掉所有的香蕉。
返回她可以在 H 小時(shí)內(nèi)吃掉所有香蕉的最小速度 K（K 為整數(shù)）祟辟。
示例 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^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9
解答
審題發(fā)現(xiàn)医瘫，速度是一個(gè)整數(shù)（有限搜索空間），并且有最大和最小范圍旧困，需要我們尋找到一個(gè)臨界點(diǎn)醇份，很顯然這類問題是要用二分法解決的。
【初始情況】
女孩吃香蕉的最小速度為1吼具，最大速度為數(shù)組中的最大值僚纷。
【邊界條件】
女孩速度較大時(shí)，一定可以快速吃完拗盒，而不被抓住怖竭，如果速度慢到一定程度，吃不完陡蝇，會(huì)被抓痊臭，抓與被抓的臨界點(diǎn)在于，速度可以剛好滿足在指定時(shí)間內(nèi)吃完登夫。
因此我們可構(gòu)造一個(gè)函數(shù)广匙，函數(shù)的輸入是吃香蕉的速度speed，函數(shù)返回值是以該速度吃香蕉會(huì)不會(huì)被抓住恼策，會(huì)被抓住返回False鸦致。
然后就是二分法的模板：
while 下限< 上限:
中點(diǎn) = (下限+上限) // 2
if 成功吃完所有香蕉以(中點(diǎn))速度:
上限 = 中點(diǎn)
else:
下限 = 中點(diǎn) + 1
from typing import List
import math
class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
slow, fast = 1, max(piles)
def possible(speed):
return sum([math.ceil(pile / speed) for pile in piles]) <= H
while slow < fast:
mid = (slow + fast) // 2
if possible(mid):
fast = mid
else:
slow = mid + 1
return slow
如有疑問或建議，歡迎評(píng)論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析
