# 「力扣」第 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 <= 500001 <= people[i] <= limit <= 30000
# 理解题意
- 题目当中很重要的信息是：每艘船最多可同时载两人；
- 保证每个人都能被船载，题目最后给出的提示也告诉我们：
people[i] <= limit。
# 解题思路
让当前体重最轻的人能够与当前体重最重的人配对（乘坐同一艘船）：
- 如果不能配对，说明 当前体重最重的人 需要单独配一艘船；
- 如果可以配对，则将他们配对（乘坐同一艘船）。
因此，可以将输入数组升序排序，在数组的头和尾分别设置一个变量 left 和 right （双指针算法）：
- 如果
people[left] + people[right] <= limit：说明left和right指向的人可以配对（乘坐同一艘船），此时left和right各向中间走一步； - 如果
people[left] + people[right] > limit：说明right指向的人太重了，他应该单独乘坐一艘船。即right向中间走一步（right--）。
按照上面的方式，直到 left 与 right 重合，这样就可以完成任务。
参考代码：
import java.util.Arrays;
public class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int len = people.length;
int res = 0;
int left = 0;
int right = len - 1;
while (left <= right) {
if (people[left] + people[right] <= limit) {
left++;
}
right--;
res++;
}
return res;
}
}
复杂度分析：
- 时间复杂度：
，这里 是输入数组的长度， left和right一起遍历了数组的长度； - 空间复杂度：
，只使用了常数个变量。
# 总结
讨论当前 最轻的人 是不是可以和当前最重的人配对（乘坐同一艘船），这样可以使得每艘船的利用率最大。这其实是「贪心算法」的思想。
作者：liweiwei1419 链接：https://suanfa8.com/two-pointers/solutions-3/0881-boats-to-save-people 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。