LeetCode 881. 救生艇
题目描述
✅ 881. 救生艇
题意分析
每条船最多载两个人，而且这两个人的总重量不能超过
limit，求把所有人都送走所需的最少船数。两条限制必须同时满足，不能因为重量还够就继续装第三个人。题目保证每个人的体重不超过限额，所以总能让每人单独乘船，不需要处理无解情况。可以任意安排谁同船，不受原输入顺序限制；总重量恰好等于限额也是合法搭配。
解法：排序 + 双指针
核心思路
[!blue]
将体重排序，
left、right分别指向尚未安排的最轻者和最重者。每轮先决定最重者怎样乘船，因为无论选哪种方案，他都必须占用一条船。如果最轻者加最重者仍超重，那么任何其他人都不会比最轻者更轻，所以最重者无法和任何人同船，必须独乘。安排掉他后，问题缩小为剩余人群，船数加一是不可避免的。
如果两者可以同船，存在一个不比最优方案差的安排把他们放在一起。若最重者原本独乘，把最轻者移到他的船上；最轻者若有原搭档，让其独乘即可，不会增加船数。若最重者原本搭配
A、最轻者原本搭配B，改成轻重同船，剩下A、B也能同船：B不重于最重者，而A原本能与最重者搭配，所以A + B不会超过限额。若其中一人原来独乘，则多出来的原搭档单独占原来的船，同样不增加船数。因此每轮都能安全地固定最重者：能带走最轻者就同时移动两端，否则只移走最重者，然后船数加一。剩下的人仍是同一个问题，重复直到没有人。若只剩一个人，他也要一条船，因此循环必须允许
left == right。
解题步骤
- 将体重原地升序排序，初始化左右端点和船数。
- 比较当前最轻与最重的重量和，不超过限额时同时安排两端，否则只安排最重者。
- 无论同船还是独乘，本轮都增加一条船，并更新剩余区间。
- 左端超过右端时说明所有人都已安排，返回船数。
代码实现
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int left = 0;
int right = people.length - 1;
int boats = 0;
// 只剩一人仍需一条船，因此保留相等边界
while (left <= right) {
if (people[left] + people[right] <= limit) {
left++;
right--;
} else {
right--;
}
// 无论配对还是独乘，本轮都安排一条船
boats++;
}
return boats;
}
}
import "sort"
func numRescueBoats(people []int, limit int) int {
sort.Ints(people)
left, right := 0, len(people)-1
boats := 0
// 只剩一人仍需一条船，因此保留相等边界
for left <= right {
if people[left]+people[right] <= limit {
left++
right--
} else {
right--
}
// 无论配对还是独乘，本轮都安排一条船
boats++
}
return boats
}
复杂度分析
- 时间复杂度：$O(n\log n)$，排序占主导，之后每个人只会被指针移出一次。
- 空间复杂度：双指针扫描使用 $O(1)$ 额外空间，标准库排序的辅助空间另按具体实现计算。
关键点总结
[!green]
- 最重者总要先占用一条船，最轻者决定这条船是否还能载第二个人。
- 两端超重时最重者必然独乘，两端可搭配时可以通过交换把最优方案改成这种搭配。
- 每一轮都使用一条船，落单者同样需要计数。
- 该贪心依赖每船最多两人的限制，不能直接推广到任意人数装载。
易错点总结
[!yellow]
- 循环只写
left < right，会漏掉最后一名独乘者。- 只有配对成功才增加船数，遗漏了无法配对的人也需要船。
- 判定使用严格小于限额，会拒绝重量恰好等于限额的合法搭配。
- 尝试往一条船不断加入更多轻者，违反最多两人的人数上限。
- 两端超重时移动最轻者，会丢掉他与其他人配对的机会，却没有解决最重者必须独乘的问题。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1877. 数组中最大数对和的最小值 | 中等 | 同样通过排序后首尾配对控制较大数对和，本题还允许单人船并最小化船数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！