题目描述（Medium）

第 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 <= 50000
1 <= people[i] <= limit <= 30000

链接：https://leetcode-cn.com/problems/boats-to-save-people

方法、排序 & 贪心 & 双指针

先理解题意：

1. 每个人的重量不会超过 limit
   ；
2. 每艘船最多只能坐两个人；
3. 每艘船的重量不能超过 limit
   ；

我们可以考虑把给定的数组排序，先选重量最大的人，看它与重量最小的人能不能合坐一艘船，如果可以，就让他们在一起，如果不可以，那么，最大重量的人肯定跟其余所有人都不能组成一对了，那就让他单着吧。然后，再看重量次大的人，同样地，看看他与重量最小的人（假设最大重量是单着的）能不能组成一对，这样子一直比下去即可。

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

1. 当重量最大的人单着的时候，其指针往中间移动一位；
2. 当重量最大的人与重量最小的人组成一对，他们俩的指针各往中间移动一位；

好了，请看代码：

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int ans = 0;

        // 从小到大排序，右边是最重的人
        Arrays.sort(people);

        int left = 0, right = people.length - 1;

        while (left <= right) {
            // 看右边的重量是否足够
            if (people[right] == limit) {
                ans++;
                right--;
            } else if (people[right] + people[left] <= limit) {
                // 再看最右边的人与最左边的人总体重量是否超过limit
                ans++;
                right--;
                left++;
            } else {
                // 还是最右边的人单着
                ans++;
                right--;
            }
        }

        return ans;
    }
}

代码有点丑，我们优化一下：

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int ans = 0;

        // 从小到大排序，右边是最重的人
        Arrays.sort(people);

        int left = 0, right = people.length - 1;

        while (left <= right) {
            // 如果最右边的人能跟最左边的人组队，左指针右移一位
            if (people[right] + people[left] <= limit) {
                left++;
            }
            // 不管如何，最右边的人这一轮循环肯定要用到
            // 同时结果加一
            ans++;
            right--;
        }

        return ans;
    }
}

• 时间复杂度：，对于 int 数组，Java使用的是双轴快排，时间复杂度为 。
• 空间复杂度：，快排使用递归实现，空间复杂度主要来自于递归栈。

运行结果如下：

最后

如果对你有帮助，请点个赞吧，谢谢^^

也可以关注我的公号【彤哥来刷题啦】，每日分享题解，一起刷题，一起拿全家桶。