题目描述
这是 LeetCode 上的 881. 救生艇 ，难度为 中等。
Tag : 「贪心」、「双指针」
第 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
贪心
一个直观的想法是：由于一个船要么载两人要么载一人，在人数给定的情况下，为了让使用的总船数最小，要当尽可能让更多船载两人，即尽可能多的构造出数量之和不超过 limitlimit 的二元组。
先对 peoplepeople 进行排序，然后使用两个指针 l 和 r 分别从首尾开始进行匹配：
- 如果 people[l] + people[r] <= limitpeople[l]+people[r]<=limit，说明两者可以同船，此时船的数量加一，两个指针分别往中间靠拢；
- 如果 people[l] + people[r] > limitpeople[l]+people[r]>limit，说明不能成组，由于题目确保人的重量不会超过 limitlimit，此时让 people[r]people[r] 独立成船，船的数量加一，
r指针左移。
我们猜想这样「最重匹配最轻、次重匹配次轻」的做法能使双人船的重量之和尽可能平均，从而使双人船的数量最大化。
接下来，我们使用「归纳法」证明猜想的正确性。
假设最优成船组合中二元组的数量为 c1c1，我们贪心做法的二元组数量为 c2c2。
最终答案 = 符合条件的二元组的数量 + 剩余人数数量，而在符合条件的二元组数量固定的情况下，剩余人数也固定。因此我们只需要证明 c1 = c2c1=c2 即可。
通常使用「归纳法」进行证明，都会先从边界入手。
当我们处理最重的人 people[r]people[r]（此时 rr 为原始右边界 n - 1n−1）时：
- 假设其与 people[l]people[l]（此时 ll 为原始左边界 00）之和超过 limitlimit，说明 people[r]people[r] 与数组任一成员组合都会超过 limitlimit，即无论在最优组合还是贪心组合中，people[r]people[r] 都会独立成船；
- 假设people[r] + people[l] <= limitpeople[r]+people[l]<=limit，说明数组中存在至少一个成员能够与people[l]people[l]成船：
- 假设在最优组合中 people[l]people[l] 独立成船，此时如果将贪心组合 (people[l], people[r])(people[l],people[r]) 中的 people[l]people[l] 拆分出来独立成船，贪心二元组数量 c2c2 必然不会变大（可能还会变差），即将「贪心解」调整成「最优解」结果不会变好；
- 假设在最优组合中，people[l]people[l]不是独立成船，又因此当前rr处于原始右边界，因此与people[l]people[l]成组的成员people[x]people[x]必然满足people[x] <= people[r]people[x]<=people[r]。 此时我们将people[x]people[x]和people[r]people[r]位置进行交换（将贪心组合调整成最优组合），此时带来的影响包括：
- 与 people[l]people[l] 成组的对象从 people[r]people[r] 变为 people[x]people[x]，但因为 people[x] <= people[r]people[x]<=people[r]，即有 people[l] + people[x] <= people[l] + people[r] <= limitpeople[l]+people[x]<=people[l]+people[r]<=limit，仍为合法二元组，消耗船的数量为 11；
- 原本位置 xx 的值从 people[x]people[x] 变大为 people[r]people[r]，如果调整后的值能组成二元组，那么原本更小的值也能组成二元组，结果没有变化；如果调整后不能成为组成二元组，那么结果可能会因此变差。
- 综上，将 people[x]people[x] 和 people[r]people[r] 位置进行交换（将贪心组合调整成最优组合），贪心二元组数量 c2c2 不会变大，即将「贪心解」调整成「最优解」结果不会变好。
对于边界情况，我们证明了从「贪心解」调整为「最优解」不会使得结果更好，因此可以保留当前的贪心决策，然后将问题规模缩减为 n - 1n−1 或者 n - 2n−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(nlogn)；双指针统计答案复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn)
- 空间复杂度：O(\log{n})O(logn)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.881 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
