救生艇 图解题解

最少几艘船能把所有人送走

每个人有一个体重，一艘船最多两人，且两人体重之和不超过上限 limit。给出体重数组 people 和 limit，求最少几艘船送走所有人，题目保证没人重到单人都坐不下。题面例子 people = [3,5,3,4,1,2,2,1]，limit = 5，答案 5 艘。

为什么不能挨个组合去试

一艘船最多两人，直觉会想枚举所有两两配对、挑用船最少的那种。可 n 人两两配对的组合数随人数爆炸增长，几十人就多到算不完。这条路把配法平等对待、逐一验算，没用上体重能排序这个信息。

最重的人必占一个船位

先把体重从小到大排好，再盯住最重的人：他这一船的位置省不掉，总得有船带上他。既然船位躲不开，就顺便看能不能塞进第二人，最划算的是当前最轻的那个。连最轻的都和他凑不进上限，更重的更不行，这船只能他独坐；最轻的能拼上就搭这一程，一次送两人。

于是配对从两端往中间收：下标 l 盯最轻、下标 r 盯最重，各自往里走，这就是双指针对撞。每一步都围着当下最重的人定这一船怎么坐、坐定就不再挪动；这种贪心最省，是因为最重者的船位本就躲不掉，我们只是在这艘躲不掉的船上顺手多捎个最轻的。

把这套配对写成代码

先给 people 排序，l 从 0、r 从末尾出发，boats 记船数。每轮看 people[l] 加 people[r]：和不超 limit 就让 l 右挪一格；无论拼没拼上最重的这船都要开，r 每轮左移、boats 加一。循环条件用 l 小于等于 r，让两指针重合时还为最后一人开一艘，直到 l 越过 r 返回 boats。

拿题面这组人过一遍配对

先排序，people = [3,5,3,4,1,2,2,1] 排成 [1,1,2,2,3,3,4,5]，l 指最左的 1、r 指最右的 5，boats 从 0 起。第一轮 1 加 5 得 6 超 5 搭不上，l 不动、r 左移到 4，boats 变 1。第二轮 1 加 4 得 5 不超，两指针各挪一步到 3，boats 变 2。第三轮 1 加 3 得 4 能拼，一起走，boats 变 3。

第四轮 2 和 3 加起来 5，又拼一艘，boats 变 4，l 和 r 收拢到中间的 2 上重合。最后一轮两指针都指这个 2，它自己凑成一船，boats 变 5，r 左移后 l 越过 r 停下。一共 5 艘船，正是题面答案。

复杂度和两个易写坏的地方

开头那次排序吃掉了大半时间，要 O(n log n)；之后双指针从两端扫到中间一遍是 O(n)，相加仍 O(n log n)。除排序外只用 l、r、boats 三个变量、没开额外数组，空间 O(1)。

有两处写着写着就错。排序不能省，最轻配最重只在有序时成立，跳过它结果会偏。r 每轮都得左移，因为最重者这船必开；只有 people[l] 加 people[r] 不超上限 l 才右移，拼不上也动 l 就把该等下一艘的最轻者提前送走了。循环条件写 l 小于等于 r，写成 l 小于 r 会在两指针重合时提前退出，漏掉最后单独坐船那人。

Python

def numRescueBoats(people, limit):
    people.sort()                 # 体重从小到大
    l, r = 0, len(people) - 1     # 最轻 / 最重
    boats = 0
    while l <= r:
        if people[l] + people[r] <= limit:
            l += 1                # 最轻的也能拼上
        r -= 1                    # 最重的人必上船
        boats += 1
    return boats

C++

int numRescueBoats(vector<int>& people, int limit){
    sort(people.begin(), people.end());
    int l = 0, r = people.size() - 1, boats = 0;
    while (l <= r) {
        if (people[l] + people[r] <= limit) l++;
        r--;
        boats++;
    }
    return boats;
}

Java

public int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int l = 0, r = people.length - 1, boats = 0;
    while (l <= r) {
        if (people[l] + people[r] <= limit) l++;
        r--;
        boats++;
    }
    return boats;
}