881. 救生艇
题目描述
输入数组 people 和整数 limit，people[i] 是第 i 个人的体重。船的数量不限。
每艘船最多坐两个人，并且船上人的体重之和不能超过 limit。保证每个人的体重都不超过 limit。
返回把所有人都运走最少需要多少艘船。
示例 1
输入：people = [1,2], limit = 3 输出：1
解释：两人体重和为 3，坐一艘船即可。
示例 2
输入：people = [3,2,2,1], limit = 3 输出：3
解释：分为 (1,2)、(2)、(3) 三艘。
示例 3
输入：people = [3,5,3,4], limit = 5 输出：4
解释：任意两人体重和都超过 5，只能每人一艘。
数据范围
1 <= people.length <= 5 * 10^41 <= people[i] <= limit <= 3 * 10^4
解题思路
先排序。最重的人一定要上船，问题是能不能给他配一个同伴。最有希望的同伴是最轻的人：如果最轻的人都配不上，别人更不可能，最重的人只能单独坐；如果能配上，让他们同船不会更差，因为最轻的人和谁坐都只占一个名额。用双指针 i（最轻）和 j（最重）向中间收缩。
为什么正确
people[:i] 和 people[j+1:] 已经上船，boats 是已经用掉的船数；剩下的 people[i..j] 还在岸上。
复杂度分析
时间 O(n log n)（排序），额外空间 O(1)（不计排序栈）。
易错点
从最轻的人开始两两凑满，或者给最重的人找“刚好能配”的最重同伴，都会让思路变复杂。只要比较最轻和最重即可；另外 i == j 时只剩一人，也要算一艘船。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
i, j = 0, len(people) - 1
boats = 0
while i <= j:
if people[i] + people[j] <= limit:
i += 1
j -= 1
boats += 1
return boatsclass Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int i = 0, j = people.length - 1;
int boats = 0;
while (i <= j) {
if (people[i] + people[j] <= limit) {
i++;
}
j--;
boats++;
}
return boats;
}
}class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
sort(people.begin(), people.end());
int i = 0, j = people.size() - 1;
int boats = 0;
while (i <= j) {
if (people[i] + people[j] <= limit) {
i++;
}
j--;
boats++;
}
return boats;
}
};func numRescueBoats(people []int, limit int) int {
sort.Ints(people)
i, j := 0, len(people)-1
boats := 0
for i <= j {
if people[i]+people[j] <= limit {
i++
}
j--
boats++
}
return boats
}var numRescueBoats = function(people, limit) {
people.sort((a, b) => a - b);
let i = 0, j = people.length - 1;
let boats = 0;
while (i <= j) {
if (people[i] + people[j] <= limit) {
i++;
}
j--;
boats++;
}
return boats;
};function numRescueBoats(people: number[], limit: number): number {
people.sort((a, b) => a - b);
let i = 0, j = people.length - 1;
let boats = 0;
while (i <= j) {
if (people[i] + people[j] <= limit) {
i++;
}
j--;
boats++;
}
return boats;
}