【LeetCode双指针】881 救生艇 Boats to Save People(java实现)

题目描述

• 给定数组 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 * 104
• 1 <= people[i] <= limit <= 3 * 104

一、解题思路

使用对撞指针解决问题，对撞指针需要数组有序。
① 排序
② 遍历数组，如果 people[i] + people[j] <= limit，则移动 i 指针，j 指针一直往前移动，直到两者相遇
③ 初始条件如下:

i = 0;
j = people.length - 1;
res = 0;

注意:循环体中，每经历一次循环之后，res[计数器 记录船的数量]都要加 1

二、代码

1.救生艇

代码如下：

class Solution {public int numRescueBoats(int[] people, int limit) {if (people == null || people.length == 0) {  // 边界情况return 0;}// 对撞指针int i = 0; int j = people.length - 1;int res = 0;Arrays.sort(people);  // 对撞指针需要数组有序，因此对数组排序while (i <= j) {  // 记录船的数量if (people[i] + people[j] <= limit) {i++;}j--;res++;}return res;}
}

2.执行时间

总结

在双指针中如果需要用到对撞指针，对撞指针要求数组有序，因此需要将数组先排序