Description
每艘船最多載兩人，且有重量上限
limit。給定每個人的體重people，回傳載完所有人所需的最少船數。
Example:
Input: people = [3,2,2,1], limit = 3 Output: 3（[1,2], [2], [3]）
Intuition#
核心思路：排序後，最重的人嘗試與最輕的人配對上同一艘船。若無法配對，最重的人獨自一船。
- 貪心策略：讓最重的和最輕的配對，能省一艘船就省
- 排序後用左右指針，若
people[left] + people[right] <= limit則配對成功，兩人一船 - 每輪無論是否配對，right 都會減一（最重的人一定會上船）
Approaches#
1: 排序 + 逐一配對（Brute Force 思維）#
- 概念: 排序後嘗試為每個人找配對，用 visited 標記
- 時間複雜度:
O(n²)- 最差每人掃一遍 - 空間複雜度:
O(n)- visited 陣列
Brute Force 程式碼
class Solution {
fun numRescueBoats(people: IntArray, limit: Int): Int {
people.sort()
val used = BooleanArray(people.size)
var boats = 0
for (i in people.indices.reversed()) {
if (used[i]) continue
used[i] = true
boats++
for (j in 0 until i) {
if (!used[j] && people[j] + people[i] <= limit) {
used[j] = true
break
}
}
}
return boats
}
}⭐2: 排序 + Two Pointers 貪心#
- 概念: 排序後左右指針，嘗試配對最輕和最重的人
- 時間複雜度:
O(n log n)- 排序主導 - 空間複雜度:
O(1)- 原地排序
class Solution {
fun numRescueBoats(people: IntArray, limit: Int): Int {
people.sort()
var left = 0
var right = people.size - 1
var boats = 0
while (left <= right) {
if (people[left] + people[right] <= limit) {
left++ // 最輕的人也上船
}
right-- // 最重的人一定上船
boats++
}
return boats
}
}注意迴圈條件是
left <= right（包含等號），因為最後一個人自己也需要一艘船。
🔑 Takeaways#
- Pattern: 排序 + 相向雙指針 + 貪心配對
- 關鍵技巧: 每艘船最多兩人的限制讓貪心配對最輕和最重成為最佳策略；right 每輪必減代表最重的人必定安排