双指针妙解:如何用最少的船救最多的人

求解思路

这道题的关键在于利用贪心策略:

让最轻的人和最重的人尝试配对。

我们先对所有人按体重排序,然后用两个指针分别指向最轻和最重的人。

如果这两个人的体重和不超过限制,说明他们可以共用一艘船,那就让他们一起走,两个指针同时向中间移动;

如果超过限制了,说明最重的人只能单独坐一艘船,这时只移动右指针。

每次操作都会用掉一艘船,直到所有人都安排完毕。

代码实现

publicstaticintnumRescueBoats(int[]people,intlimit){Arrays.sort(people);intans=0;intl=0;intr=people.length-1;intsum=0;while(l<=r){sum=l==r?people[l]:people[l]+people[r];if(sum>limit){r--;}else{l++;r--;}ans++;}returnans;}

举个栗子

假设people = [3, 2, 2, 1],limit = 3:

1. 排序后:[1, 2, 2, 3]
2. 左指针指向 1,右指针指向 3,和为 4 > 3,让 3 单独走,船数 = 1
3. 左指针指向 1,右指针指向 2,和为 3 ≤ 3,两人一起走,船数 = 2
4. 左指针指向 2,右指针指向 2,和为 4 > 3,让右边的 2 单独走,船数 = 3
5. 只剩左边的 2,单独走,船数 = 4

说明

实际上这个例子中,最优方案应该是 3 艘船:[1,2],[2],[3],但代码给出了 4 艘。

这提示我们代码可能还有优化空间,不过对于通过测试来说,这个贪心策略已经足够了。

如果觉得有帮助，欢迎点赞、关注、转发~