LeetCode 881. 救生艇

2026-03-27 HGNULB 约 8 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 881. 救生艇

题意分析

题目给一组人的体重和一个载重上限，每条船有两条硬约束：最多坐两个人，且船上人的体重之和不超过上限。要把所有人都送走，问最少需要几条船。

「最多两人」这条限制是整道题的题眼。如果没有它，这就是经典的装箱问题，属于 NP 难；正是因为一条船最多两人，问题才从「怎么装」退化成「谁和谁配对」，也才有了多项式解法。

约束里另一条关键信号是题目保证每个人的体重都不超过载重上限，所以任何人至少能单独乘一条船，答案一定存在，不必处理无解。人数最大 $5 \times 10^4$，允许排序，也允许一次线性扫描。

边界上要留意：人数为奇数时必然有人落单；两个人体重之和恰好等于上限是允许的，判定要用不超过而不是严格小于；所有人都很重时答案就是人数本身。

解法：排序 + 双指针

核心思路

朴素想法是枚举所有配对方案，看哪种用船最少。$n$ 个人的配对方案数是阶乘量级，在 $5 \times 10^4$ 的规模下毫无可能。

换个角度想：每条船最多两人，所以船数等于「落单的人数加上配对数」，而总人数固定，于是最小化船数完全等价于最大化配对数。问题被翻译成了一个纯粹的匹配问题：尽可能多地把人两两配起来，使每对的体重和不超过上限。

瓶颈变成了怎样确定配对方式。这时排序开始起作用。把体重升序排好后，考虑当前还没安排的人里最重的那个——他终归要上船，问题只是有没有人能陪他。能陪他的人必须满足体重和不超上限，而在所有还没安排的人里，最轻的那个是最有可能满足这一条的；如果连最轻的人都陪不了他，那谁也陪不了，他只能独占一条船。

反过来，如果最轻的人陪得了他，那么让这两人同船一定不劣，这一步需要交换论证来撑住。记最重的人为 $H$、最轻的人为 $L$，前提是 $L + H \leq \text{limit}$。任取一个最优方案：若 $H$ 与另一人 $x$ 同船、$L$ 与另一人 $y$ 同船，就改成 $H$ 与 $L$ 同船、$x$ 与 $y$ 同船——前一条船合法是前提，后一条也合法，因为 $y \leq H$（$H$ 是最重的），所以 $x + y \leq x + H \leq \text{limit}$，船数不变；若 $H$ 有伴而 $L$ 独占，把 $H$ 的伴换成 $L$、让原来的伴独占，船数不变；若 $H$ 独占而 $L$ 有伴，让 $L$ 转去陪 $H$、原来的伴独占，船数还是不变；若两人各自独占，合成一条船反而更省。四种情形无一变差，说明总存在一个最优方案让 $L$ 与 $H$ 同船，这一步贪心是安全的。

落到实现上，用两个指针 left 与 right 分别指向未安排的人里最轻和最重的那位，维护不变量：闭区间 $[\text{left}, \text{right}]$ 恰好是所有尚未上船的人，且区间内体重仍然升序；boats 等于已经开出的船数。每一轮必定安排掉 right 这个人（消耗一条船），并且只在 people[left] + people[right] 不超过上限时顺带把 left 也送走。区间一轮至少缩短一格，循环必然终止。

当 left 和 right 指向同一个人时，判定式比较的是这个人和他自己，无论结果落在哪个分支，本轮都只加一条船、区间随后清空，答案都是对的——这个巧合让代码不需要为奇数人数写任何特判。

解题步骤

先把体重数组升序排序。为什么必须排序：整个贪心的依据是「未安排的人里最轻的最有可能陪最重的」，这句话只有在有序时才能用 $O(1)$ 拿到两端。

令 left = 0、right = n - 1、boats = 0。为什么 right 是 $n - 1$：它是下标而非长度，指向当前最重的人。

当 left <= right 时循环。为什么是小于等于而不是小于：区间里只剩一个人时他也需要一条船，写成严格小于会把这个人漏掉。

每轮先判断 people[left] + people[right] <= limit。成立就同时 left++ 和 right--，表示这两人合乘一条船；不成立就只 right--，表示最重的人独占一条船。为什么不成立时可以直接判他独占：数组有序，最轻的人都超载，其余人只会更重，没有任何人能与他同船。

无论走哪个分支，本轮都执行一次 boats++。为什么两个分支都要加：两种情况都恰好开出一条船，区别只在这条船上坐了一个人还是两个人。

循环结束返回 boats。

以 people = [3,2,2,1], limit = 3 走一遍：排序后数组是 [1,2,2,3]，left = 0、right = 3、boats = 0。

第一轮：people[0] + people[3] = 1 + 3 = 4，大于上限 3，说明最轻的 1 也陪不了体重 3 的人，他独占一条船。只执行 right-- 得到 right = 2，boats 变成 1。待安排的人是下标 0 到 2，即体重 [1,2,2]。

第二轮：people[0] + people[2] = 1 + 2 = 3，恰好等于上限，允许同船。left 变成 1、right 变成 1，boats 变成 2。待安排的只剩下标 1 这个体重为 2 的人。

第三轮：left 与 right 都是 1，判定式算的是 people[1] + people[1] = 2 + 2 = 4，超过上限，于是走独占分支，只执行 right-- 得到 right = 0，boats 变成 3。此时这个人已被安排掉。

第四轮检查循环条件：left = 1 大于 right = 0，退出。返回 3。

复核这个答案：三条船分别载「体重 3」「体重 1 和 2」「体重 2」，每条都不超载且不超过两人；而四个人里体重和不超过 3 的配对只有 $1 + 2$ 这一种（$2 + 2 = 4$、$1 + 3 = 4$ 都超），最多只能配成一对，落单三人变两人，船数下限正是 $4 - 1 = 3$，与贪心结果吻合。

代码实现

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;
    }
}

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)$，其中 $n$ 是人数。排序是唯一的瓶颈；之后的双指针循环里，left 只增、right 只减，两者合计移动不超过 $n$ 步，每步只做一次加法和一次比较，是 $O(n)$。

空间复杂度：$O(\log n)$，算法本身只用了三个整型变量，额外开销全部来自对基本类型数组的原地快速排序所需的递归栈；若把排序视为已完成，则是 $O(1)$。

关键点总结

遇到最小化「容器数」的题，先把它翻译成最大化「配对数」。这一步转换把带约束的最优化问题变成了纯匹配问题，思路立刻清晰。

「一条船最多两人」是让贪心成立的命门。要清楚地知道，容量放宽到三人以上时问题就退化成装箱，本题的解法不再适用，这是理解深度的分水岭。

排序后从两端夹逼的贪心，必须能说出交换论证，而不是「感觉最轻配最重比较划算」。论证里真正起作用的一步是 $y \leq H$，靠的正是 $H$ 是当前最重的人这一事实。

让循环不变量携带「区间恰是未处理元素」的语义，边界条件就不用背：只剩一个人时区间非空，所以循环条件必须取小于等于。

面试视角：这题写完只有十行，面试官的分数几乎全押在贪心正确性的解释上。主动给出交换论证，再顺手说明 left == right 时为什么不需要特判，就基本满分了。

面试视角：常见追问是「怎么证明这就是最少船数」。可以给出下界论证——船数等于人数减去配对数，而贪心得到的配对数是最大匹配，两者相减自然最小；也可以反过来指出，每条船至多消化两人，所以船数不会低于人数的一半。

易错点总结

错误写法：忘记先排序就直接双指针。用例 people = [3,1,2,2], limit = 3 → 首轮拿 3 与末位 2 相加超限，之后一路只移动右指针，返回 4，正确答案是 3。

错误写法：循环条件写成 left < right。用例 people = [3,2,2,1], limit = 3 → 区间收缩到只剩一个人时直接退出，那个人没被安排，返回 2，正确答案是 3。

错误写法：把 boats++ 只放在配对成功的分支里。用例 people = [3,2,2,1], limit = 3 → 只有第二轮计了数，返回 1，正确答案是 3。

错误写法：配对成功时只移动 left 而忘了移动 right。用例 people = [1,2], limit = 3 → 第一轮配对后右指针仍指着体重 2 的人，第二轮让他和自己配失败又开一条船，返回 2，正确答案是 1。

错误写法：判定式漏掉等号，写成 people[left] + people[right] < limit。用例 people = [1,2], limit = 3 → 和恰好等于 3 却被判超载，两人各占一条船，返回 2，正确答案是 1。

错误写法：贪心方向取成「让最重的两个人尽量同船」，两个指针都从大端往小端走。用例 people = [1,1,3,3], limit = 4 → 两个 3 无法同船各占一条，剩下两个 1 合乘一条，返回 3，正确答案是 2（每条船各载一个 3 和一个 1）。

错误写法：忽略「每条船最多两人」，按累加不超载就一直往同一条船上塞。用例 people = [1,1,1], limit = 3 → 三人被塞进一条船，返回 1，正确答案是 2。

错误写法：right 用 people.length 初始化。用例任意输入 → 首次访问 people[people.length] 直接数组越界。

相似题目

题目	难度	考察点
455. 分发饼干	简单	两个有序序列间的一对一匹配，目标是最大化满足人数
167. 两数之和 II - 输入有序数组	中等	依据和与目标的大小关系移动指针，找唯一一组解
11. 盛最多水的容器	中等	收缩依据是「短板决定面积」，与配对可行性无关
621. 任务调度器	中等	同为贪心排布，但靠最高频元素推导下界公式而非双指针