Medium

题目描述

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

解题思路

这是一个经典的贪心算法问题。关键思路是通过双指针技术最大化每艘船的利用率。

核心思想： 首先对人员体重进行排序，然后使用双指针分别指向最轻和最重的人。由于每艘船最多载两人，我们有以下策略：

  1. 如果最轻的人和最重的人的体重之和不超过限制，说明可以同时载两人，两个指针都移动
  2. 如果超过限制，说明最重的人必须单独乘船，只移动右指针

算法流程：

  • 对 people 数组排序
  • 设置左指针 left=0，右指针 right=n-1
  • 统计船只数量 boats=0
  • 当 left <= right 时：
    • 如果 people[left] + people[right] <= limit，left++（最轻的人也上船）
    • right–（最重的人上船）
    • boats++

这种贪心策略是正确的，因为如果最重的人无法与最轻的人同船，那么他也无法与任何其他人同船，只能独自乘船。

代码实现

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int left = 0, right = people.size() - 1;
        int boats = 0;
        
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            boats++;
        }
        
        return boats;
    }
};

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        left, right = 0, len(people) - 1
        boats = 0
        
        while left <= right:
            if people[left] + people[right] <= limit:
                left += 1
            right -= 1
            boats += 1
            
        return boats

public class Solution {
    public int NumRescueBoats(int[] people, int limit) {
        Array.Sort(people);
        int left = 0, right = people.Length - 1;
        int boats = 0;
        
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            boats++;
        }
        
        return boats;
    }
}

var numRescueBoats = function(people, limit) {
    people.sort((a, b) => a - b);
    let left = 0, right = people.length - 1;
    let boats = 0;
    
    while (left <= right) {
        if (people[left] + people[right] <= limit) {
            left++;
        }
        right--;
        boats++;
    }
    
    return boats;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要开销在排序，双指针遍历为 O(n)
空间复杂度O(1)只使用常量额外空间（不考虑排序的空间开销）