LeetCode 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)

提示：

• 1 <= people.length <= 5 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4

二、题目解析

三、参考代码

Python

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:

        # 先排序
        people.sort()

        # 获取数组长度
        n = len(people)

        # 寻找两人组

        # 最左边的位置
        left = 0

        # 最右边的位置
        right = n - 1

        # 船的数量
        ans = 0

        while left <= right :
            
            # 1、如果 people[left] + people[right] <= limit
            # 说明 people[left] 和 people[right] 可以同船
           
            if people[left] + people[right] <= limit :

                #  此时船的数量加一
                ans += 1

                # 两个指针分别往中间靠拢

                left += 1

                right -= 1

                
            # 如果 people[left] + people[right] > limit
            # 说明 people[left] 和 people[right] 不可以同船
            else:

                # 由于题目说明了人的重量不会超过 limit
                # people[right] 需要独自坐船，船的数量加一
                ans += 1

                # people[right] 坐船后
                # right 需要向内移动，寻找新的组合
                right -= 1

        # 返回结果
        return ans

Java

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int n = people.length;
        int left = 0;
        int right = n - 1;
        int ans = 0;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                ans++;
                left++;
                right--;
            } else {
                ans++;
                right--;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        // 先对数组进行排序
        sort(people.begin(), people.end());

        // 获取数组长度
        int n = people.size();

        // 定义两个指针分别指向数组的两端
        int left = 0;          // 最左边的位置
        int right = n - 1;     // 最右边的位置

        // 记录所需的船的数量
        int ans = 0;

        // 当左指针小于等于右指针时，继续寻找组合
        while (left <= right) {

            // 1、如果 people[left] + people[right] <= limit
            // 说明 people[left] 和 people[right] 可以同船
            if (people[left] + people[right] <= limit) {
                // 船的数量加一
                ans += 1;

                // 两个指针分别向中间移动
                left += 1;
                right -= 1;
            }

            // 如果 people[left] + people[right] > limit
            // 说明 people[left] 和 people[right] 不可以同船
            else {
                // 根据题目，人的重量不会超过 limit
                // people[right] 需要独自坐船，船的数量加一
                ans += 1;

                // people[right] 坐船后，right 向内移动，寻找新的组合
                right -= 1;
            }
        }

        // 返回总的船的数量
        return ans;
    }
};