881. 救生艇
给定数组 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)
题目来源：力扣（LeetCode）
对撞双指针思路
能否写出：能写出。
时间：10多分钟
思路：
首先，对数组 people 进行排序，将人的体重按升序排列，这样可以方便后续的处理。
- 使用两个指针
i和j分别指向数组的开头和结尾。 - 进行循环，条件是
i <= j，即还有人需要运送。 - 在循环中，计算指针
i和j对应的人的体重之和total。 - 如果
total小于等于限制值limit，说明这两个人可以坐在同一艘船上。此时，将船数result加一，同时将指针i和j分别向后移动一位，继续处理下一对人。 - 如果
total大于限制值limit，说明只能将指针j对应的人单独放在一艘船上。此时，将指针j向前移动一位，继续处理下一对人。 - 循环结束后，返回最少需要的船数
result。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public int numRescueBoats(int[] people, int limit) { int count = 0; Arrays.sort(people); int left = 0; int right = people.length-1; while (left<=right){ int total = people[left]+people[right]; if(total<=limit){ count++; left++; right--; continue; } right--; count++; } return count; } }
简化：
class Solution { public int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int left = 0; int right = people.length - 1; int count = 0; while (left <= right) { if (people[left] + people[right] <= limit) { left++; right--; } else { right--; } count++; } return count; } }
时间复杂度：O(nlogn) 有额外消耗在排序上
空间复杂度：O(logn)
