題目描述:
給定一個整數陣列 people,其中 people[i] 是第 i 個人的體重,以及一個整數 limit 表示每艘船的載重上限。每艘船最多載兩人,且總重量不超過 limit。求最少需要幾艘船才能載完所有人。
解題思路: 排序 + 雙指標(貪心):
people 排序。lo(最輕的人)和右指標 hi(最重的人)。people[lo] + people[hi] <= limit,兩人共乘一船,lo++、hi--。hi--。貪心正確性:最重的人若無法與最輕的人同船,則他無法與任何人同船,必須獨佔一艘。若能同船,讓最輕的人搭配是最優的(為其他人保留更大的配對空間)。
時間複雜度:O(n log n) — 排序為主要開銷,雙指標掃描為 O(n)。
空間複雜度:O(log n) — 排序所需的棧空間(原地排序)。
1. Sort people array in ascending order. 2. Initialize lo = 0, hi = n - 1, boats = 0. 3. While lo <= hi: a. If people[lo] + people[hi] <= limit: increment lo (pair them). b. Decrement hi (heaviest person boards). c. Increment boats. 4. Return boats.
計數排序 + 雙指標:若體重範圍有限(如 1 到 limit),可用計數排序將時間降至 O(n + limit)。適用於體重值域小的情況,但一般排序已足夠。
暴力枚舉配對:O(n^2) 嘗試所有配對。效率太低,不適用於大規模輸入。