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），而且每艘船最多只能坐两个人。你要用最少的船把所有人运过去。这就是这道题要解决的问题。

比如，有两个人，体重分别是1和2，船限重3，那他们可以一起坐一艘船。但如果有三个人，体重分别是3、2、2，限重还是3，那最重的3只能自己坐一艘船，剩下的两个2虽然都是2，但加起来是4，超过3了，所以也只能各坐一艘船，总共需要3艘船。

思路是怎么来的

你可能会想：怎么安排才能用最少的船呢？一个直觉是：尽量让两个人一起坐船，因为这样能省船。但两个人一起坐船有个条件：他们的体重加起来不能超过限重。

那怎么配对最划算？想象一下：最重的那个人最难找搭档，因为他体重太大，很少有人能和他一起坐。所以我们应该优先处理最重的人。对于最重的人，最好的搭档是谁？当然是目前最轻的那个人。因为最轻的人体重最小，最有可能和最重的人凑在一起不超过限重。如果最轻的人都和最重的人凑不上，那最重的人就只能自己坐船了。

这个思路叫“贪心策略”：每次都做当前看起来最划算的选择。具体来说，就是先给所有人按体重排个队，最轻的站左边，最重的站右边。然后让最轻的人和最重的人试着配对。如果成功，就一起走；如果失败，就让最重的人自己走。然后继续处理剩下的人。

为什么这样能保证船最少？因为最重的人如果和最轻的人都配不上，那和其他人更配不上，只能自己走，这是最优选择。而如果配得上，那让他们一起走是最省船的，因为最轻的人走了，剩下的人体重都比较大，更容易配对。

代码逐步拆解

我们来看参考代码，一行一行解释。

import java.util.Arrays;

这行是引入Java里的排序工具，因为我们要给体重排序。

class Solution {
    public int numRescueBoats(int[] people, int limit) {

这里定义了一个方法，输入是所有人的体重数组和船的限重，输出是最少需要的船数。

        Arrays.sort(people);

这行把所有人的体重从小到大排序。比如输入是[3,2,2,1]，排序后就变成[1,2,2,3]。排序是为了方便我们找最轻和最重的人。

        int n = people.length;
        int left = 0;
        int right = n - 1;
        int ans = 0;

• n 是总人数。
• left 指向最轻的人，初始在最左边，也就是体重最小的那个人。
• right 指向最重的人，初始在最右边，也就是体重最大的那个人。
• ans 用来记录已经用了多少艘船，初始是0。

        while (left <= right) {

这个循环会一直执行，直到左边指针超过右边指针，也就是所有人都安排完了。注意条件是 left <= right，因为当 left == right 时，还有一个人没处理。

            if (people[left] + people[right] <= limit) {
                ans++;
                left++;
                right--;
            } else {
                ans++;
                right--;
            }

这是核心逻辑：

• 先看最轻的人（people[left]）和最重的人（people[right]）能不能一起坐船（体重和不超过限重）。
• 如果能（<= limit），就让他们一起走，船数加1，然后左边指针右移（最轻的人走了），右边指针左移（最重的人走了）。
• 如果不能（> limit），那就让最重的人自己走，船数加1，只有右边指针左移（最重的人走了），最轻的人还留着，等下一轮再配对。

举个例子，people = [1,2,2,3], limit = 3：