傳送帶上有
weights代表的包裹（必須按順序運送），船的載重量為capacity。每天船會裝載包裹直到無法再裝（不能超重）。求在days天內運完所有包裹的最小船載重量。
Example:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15
Intuition
TIP
在答案空間 [max(weights), sum(weights)] 上二分搜尋，找最小的載重量使得能在 days 天內完成。
- 載重量越大，需要的天數越少 — 具有單調性
- 最小載重量為
max(weights)（至少要能裝下最重的包裹） - 最大載重量為
sum(weights)（一天全部運完）
Approaches
1. Linear Search — O(n * sum(weights)) / O(1)
- Idea: 從
max(weights)開始逐一嘗試載重量 - Time:
O(n * sum(weights)) - Space:
O(1)
Linear Search Code
class Solution {
fun shipWithinDays(weights: IntArray, days: Int): Int {
var cap = weights.max()
while (true) {
if (canShip(weights, days, cap)) return cap
cap++
}
}
private fun canShip(weights: IntArray, days: Int, cap: Int): Boolean {
var daysNeeded = 1
var currentLoad = 0
for (w in weights) {
if (currentLoad + w > cap) {
daysNeeded++
currentLoad = 0
}
currentLoad += w
}
return daysNeeded <= days
}
}⭐ 2. Binary Search on Answer Space — O(n * log(sum(weights))) / O(1)
- Idea: 在 [max(weights), sum(weights)] 上二分搜尋最小可行的載重量
- Time:
O(n * log(sum(weights))) - Space:
O(1)
class Solution {
fun shipWithinDays(weights: IntArray, days: Int): Int {
var left = weights.max()
var right = weights.sum()
while (left < right) {
val mid = left + (right - left) / 2
if (canShip(weights, days, mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
private fun canShip(weights: IntArray, days: Int, cap: Int): Boolean {
var daysNeeded = 1
var currentLoad = 0
for (w in weights) {
if (currentLoad + w > cap) {
daysNeeded++
currentLoad = 0
}
currentLoad += w
}
return daysNeeded <= days
}
}WARNING
與 Koko Eating Bananas (#875) 是同一個模式：在答案空間上二分搜尋最小可行值。差別在於 feasibility check 的實作不同。
🔑 Takeaways
- Pattern: Binary Search on Answer（在答案空間上二分搜尋最小可行值）
- Key trick: 寫好
canShip()判斷函式是關鍵。貪心地裝載：盡量裝滿每天的船，裝不下就換一天