LC 881. 救生艇

题目描述

这是 LeetCode 上的 881. 救生艇 ，难度为 中等。

第 i 个人的体重为 people[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 <= 50000
• 1 <= people[i] <= limit <= 30000

---

贪心

一个直观的想法是：由于一个船要么载两人要么载一人，在人数给定的情况下，为了让使用的总船数最小，要当尽可能让更多船载两人，即尽可能多的构造出数量之和不超过 $limit$ 的二元组。

先对 $people$ 进行排序，然后使用两个指针 l 和 r 分别从首尾开始进行匹配：

• 如果 $people[l] + people[r] <= limit$，说明两者可以同船，此时船的数量加一，两个指针分别往中间靠拢；
• 如果 $people[l] + people[r] > limit$，说明不能成组，由于题目确保人的重量不会超过 $limit$，此时让 $people[r]$ 独立成船，船的数量加一，r 指针左移。

我们猜想这样「最重匹配最轻、次重匹配次轻」的做法能使双人船的重量之和尽可能平均，从而使双人船的数量最大化。

接下来，我们使用「归纳法」证明猜想的正确性。

假设最优成船组合中二元组的数量为 $c1$，我们贪心做法的二元组数量为 $c2$。

最终答案 = 符合条件的二元组的数量 + 剩余人数数量，而在符合条件的二元组数量固定的情况下，剩余人数也固定。因此我们只需要证明 $c1 = c2$ 即可。

通常使用「归纳法」进行证明，都会先从边界入手。

当我们处理最重的人 $people[r]$（此时 $r$ 为原始右边界 $n - 1$）时：

• 假设其与 $people[l]$（此时 $l$ 为原始左边界 $0$）之和超过 $limit$，说明 $people[r]$ 与数组任一成员组合都会超过 $limit$，即无论在最优组合还是贪心组合中，$people[r]$ 都会独立成船；

• 假设 $people[r] + people[l] <= limit$，说明数组中存在至少一个成员能够与 $people[l]$ 成船：

  • 假设在最优组合中 $people[l]$ 独立成船，此时如果将贪心组合 $(people[l], people[r])$ 中的 $people[l]$ 拆分出来独立成船，贪心二元组数量 $c2$ 必然不会变大（可能还会变差），即将「贪心解」调整成「最优解」结果不会变好；

  • 假设在最优组合中，$people[l]$ 不是独立成船，又因此当前 $r$ 处于原始右边界，因此与 $people[l]$ 成组的成员 $people[x]$ 必然满足 $people[x] <= people[r]$。
    此时我们将 $people[x]$ 和 $people[r]$ 位置进行交换（将贪心组合调整成最优组合），此时带来的影响包括：

    • 与 $people[l]$ 成组的对象从 $people[r]$ 变为 $people[x]$，但因为 $people[x] <= people[r]$，即有 $people[l] + people[x] <= people[l] + people[r] <= limit$，仍为合法二元组，消耗船的数量为 $1$；

    • 原本位置 $x$ 的值从 $people[x]$ 变大为 $people[r]$，如果调整后的值能组成二元组，那么原本更小的值也能组成二元组，结果没有变化；如果调整后不能成为组成二元组，那么结果可能会因此变差。

      综上，将 $people[x]$ 和 $people[r]$ 位置进行交换（将贪心组合调整成最优组合），贪心二元组数量 $c2$ 不会变大，即将「贪心解」调整成「最优解」结果不会变好。

对于边界情况，我们证明了从「贪心解」调整为「最优解」不会使得结果更好，因此可以保留当前的贪心决策，然后将问题规模缩减为 $n - 1$ 或者 $n - 2$，同时数列仍然满足升序特性，即归纳分析所依赖的结构没有发生改变，可以将上述的推理分析推广到每一个决策的回合（新边界）中。

至此，我们证明了将「贪心解」调整为「最优解」结果不会变好，即贪心解是最优解之一。

代码：

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

• 时间复杂度：排序复杂度为 $O(n\log{n})$；双指针统计答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(\log{n})$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.881 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。