# **Leetcode筆記(Koko Eating Bananas)**

:::info
:information_source: 題目 : Koko Eating Bananas, 類型 : binary search , 等級 : medium
日期 : 2023/06/29，2024/10/04
:::

### 嘗試
2024/10/04

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)

        while l < r:
            speed = (l + r) // 2
            temp_h = 0
            for p in piles:
                temp_h += math.ceil(p / speed)
            if temp_h > h:
                l = speed + 1
            elif temp_h <= h:
                r = speed
            
        return l

---
### **優化**
好可愛!科科吃香蕉
題目是問說koko可以以哪個最慢的速度(k)吃完香蕉

用l,r去逼近，設定r值最大為max(piles)(如果連最大值都沒辦法在時間內吃完，那其它更小值就不用想了)(最大值的意思是，一個小時內能吃最多香蕉，所以是一個非常寬鬆的條件，題目想要找的是一個小時內能吃最少的香蕉)

然後koko本身吃東西的規則是無條件進位法

math.ceil(num)

這個算法的時間複雜度為O(log(max(piles)) * n)，其中n是香蕉堆的數量，因為它使用二分查找的方法來找到最小的吃香蕉速度。

而空間複雜度則為O(1)，因為算法只使用了常數級別的額外空間。

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)

        while l <= r:
            speed = (l + r) // 2
            hours = 0
            for p in piles:
                hours += math.ceil(p / speed)
            if hours > h: # 不合格 往上找
                l = speed + 1
            else: # 合格 繼續往下找
                r = speed - 1
        
        return l # ????為什麼最後是回傳l 不是speed

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://blog.csdn.net/fuxuemingzhu/article/details/82716042
Provided by. 负雪明烛

###### tags: `binary search` `medium` `leetcode` `值得再想`