付費限定文章

二分搜尋: Koko吃香蕉 Koko Eating Bananas_Leetcode #875 精選75題

Giorgio Trovato on Unsplash

題目敘述

題目會給定一個輸入陣列piles，代表每堆香蕉所擁有的香蕉數量，和
一個時間上限h小時。

Koko喜歡吃香蕉，每小時可以吃k個香蕉，請問k值最少需要多少，才能讓Koko在h小時內吃完所有的香蕉？

題目的原文敘述

測試範例

Example 1:

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

Example 2:

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

Example 3:

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

約束條件

Constraints:

• 1 <= piles.length <= 10^4

香蕉最少有一堆，最多有一萬堆。

• piles.length <= h <= 10^9

時間上限h介於香蕉總堆數~十億之間。

• 1 <= piles[i] <= 10^9

每堆香蕉最少含有一根香蕉，最多有十億根香蕉。

演算法 二分搜尋法

從題意上推敲，可以知道，進食的速率和完成時間為負相關。

吃的越快，所需完食時間越少。

吃的越慢，所需完食時間越多。

輸入輸出曲線具有已排序(逆序)的性質，因此可以用二分搜尋法Binary search去找出能剛好在h小時內完食的進食速率k的最小值。