日拱算法：双指针解“救生艇”问题

本篇带来 “救生艇”问题的救生艇双指针解法~冲~~

题目：

给定数组 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)

作者：掘金安东尼

链接：https://juejin.cn/post/7062623455652347911

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，针解非商业转载请注明出处。问题

注：

1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104

解题思路

题意拆解：

每个人的救生艇重量不会超过 limit;每艘船最多只能坐两个人;每艘船的重量不能超过 limit;

我们可以考虑把给定的数组排序，先选重量最大的日拱人，云南idc服务商看它与重量最小的算法双人能不能合坐一艘船，如果可以，针解就让他们在一起，问题如果不可以，那么，最大重量的人肯定跟其余所有人都不能组成一对了，那就让他单着。

然后，再看重量次大的人，同样地，看看他与重量最小的人(假设最大重量是单着的)能不能组成一对，这样子一直比下去即可。

不失一般性地，我们先排好序，然后考虑使用双指针，初始时，香港云服务器两个指针指向两头：

当重量最大的人单着的时候，其指针往中间移动一位;

当重量最大的人与重量最小的人组成一对，他们俩的指针各往中间移动一位;

代码思路：

排序初始化双指针遍历，每次都用最重的和最轻的配对，如果两人体重小于等于limit，轻的上船(left++)。不论最轻的是否上船重的都要上船(right--)。所需船数加一(nums++)

JavaScript 实现：

/

**

* @param { number[]} people

* @param { number} limit

* @return { number}

*/

var numRescueBoats = function(people, limit) {

people.sort((a,b)=>(a-b))

let left = 0

let right = people.length-1

let nums=0

while(left<=right){

if(people[left]+people[right]<=limit){

left++

}

right--

nums++

}

return nums

};

作者：掘金安东尼

链接：https://juejin.cn/post/7062623455652347911

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

亿华云计算