华为 OD 训练营 · 题解精讲
LC881. 救生艇
LC881. 救生艇
题目描述
给定数组 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 * 10^4 1 <= people[i] <= limit <= 3 * 10^4
题目解析
解题思路
题目要求最小船数，核心约束是每船最多两人且总重不超过 limit。贪心策略是：让最重的人与最轻的人配对，若超重则重者单独乘船。这样能最大化利用船的载重，从而减少船数。
用到的算法/数据结构：排序 + 双指针（对撞指针）。排序后，用 left 指向最轻的人，right 指向最重的人，逐步向中间靠拢。
关键步骤
1. 排序：将 people 升序排列，便于双指针操作。 2. 初始化指针：left = 0，right = n-1，ans = 0。 3. 循环配对：当 left <= right 时：
- 若
people[left] + people[right] <= limit：两人同船，ans++，left++，right--。 - 否则：最重的人单独乘船，
ans++，仅right--。
4. 返回 `ans`。
示意图（以 people = [1,2,2,3], limit = 3 为例）：
初始: left=0(1), right=3(3) → 1+3>3 → 3单独, ans=1, right=2
left=0(1), right=2(2) → 1+2≤3 → 同船, ans=2, left=1, right=1
left=1(2), right=1(2) → 2+2>3 → 2单独, ans=3, right=0
left=1 > right=0 → 结束
结果: ans=3复杂度分析
- 时间复杂度：
O(n log n)，主要来自排序；双指针遍历为O(n)。 - 空间复杂度：
O(log n)或O(n)，取决于排序算法的额外空间（Python 的sort()为O(n)）。
参考代码
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
# 先排序
people.sort()
# 获取数组长度
n = len(people)
# 寻找两人组
# 最左边的位置
left = 0
# 最右边的位置
right = n - 1
# 船的数量
ans = 0
while left <= right :
# 1、如果 people[left] + people[right] <= limit
# 说明 people[left] 和 people[right] 可以同船
if people[left] + people[right] <= limit :
# 此时船的数量加一
ans += 1
# 两个指针分别往中间靠拢
left += 1
right -= 1
# 如果 people[left] + people[right] > limit
# 说明 people[left] 和 people[right] 不可以同船
else:
# 由于题目说明了人的重量不会超过 limit
# people[right] 需要独自坐船，船的数量加一
ans += 1
# people[right] 坐船后
# right 需要向内移动，寻找新的组合
right -= 1
# 返回结果
return ans