LeetCode 题解工作台
救生艇
给定数组 people 。 people[i] 表示第 i 个人的体重 ， 船的数量不限 ，每艘船可以承载的最大重量为 limit 。 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit 。 返回 承载所有人所需的最小船数 。 示例 1： 输入： people = [1,2], li…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
排序后，使用双指针分别指向数组首尾，每次取两个指针指向的元素之和与 `limit` 比较，如果小于等于 `limit`，则两个指针同时向中间移动一位，否则只移动右指针。累加答案即可。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 为数组 `people` 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
示例 1：
输入：people = [1,2], limit = 3 输出：1 解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3 输出：3 解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5 输出：4 解释：4 艘船分别载 (3), (3), (4), (5)
提示：
1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104
解题思路
方法一：贪心 + 双指针
排序后，使用双指针分别指向数组首尾，每次取两个指针指向的元素之和与 limit 比较，如果小于等于 limit，则两个指针同时向中间移动一位，否则只移动右指针。累加答案即可。
时间复杂度 ，空间复杂度 。其中 为数组 people 的长度。
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
ans = 0
i, j = 0, len(people) - 1
while i <= j:
if people[i] + people[j] <= limit:
i += 1
j -= 1
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate shows understanding of greedy algorithms by selecting optimal pairs.
- question_mark
The candidate efficiently uses a two-pointer approach to minimize boats used.
- question_mark
The candidate handles edge cases such as when all people exceed the boat limit by themselves.
常见陷阱
外企场景- error
Failing to handle the case where no one can be paired due to extreme weight differences.
- error
Incorrectly using a brute force approach, which results in higher time complexity than necessary.
- error
Not properly managing edge cases where the number of people is small or where everyone has the same weight.
进阶变体
外企场景- arrow_right_alt
What if the boat can carry more than two people at a time?
- arrow_right_alt
How would the problem change if there is a weight range restriction for pairing?
- arrow_right_alt
What if some boats can carry additional weight but with a cost?