本文共 1557 字，大约阅读时间需要 5 分钟。

要解决这个问题，我们需要找到最少的船数，使得每个人的体重不超过船的最大载重量，并且每条船最多载两个人。以下是详细的解决方案：

方法思路

这种方法的时间复杂度主要由排序操作决定，为O(n log n)，而双指针遍历的时间复杂度为O(n)，因此总体复杂度为O(n log n)，适用于题目给定的约束条件。

解决代码

import java.util.Vector;
public class Solution {
    public int numRescueBoats(Vector
   
     people, int limit) {
        // 对人数组进行排序
        for (int i = 0; i < people.size(); i++) {
            for (int j = i + 1; j < people.size(); j++) {
                if (people[i] > people[j]) {
                    // 交换位置
                    int temp = people[i];
                    people.set(i, people[j]);
                    people.set(j, temp);
                }
            }
        }
        int ans = 0;
        int l = 0, r = people.size() - 1;
        while (l <= r) {
            // 当前两个人的总重量
            int sum = people[l] + people[r];
            if (sum <= limit) {
                // 两个人可以一起乘船
                l++;
                r--;
                ans++;
            } else {
                // 右边的人单独乘船
                ans++;
                r--;
            }
        }
        return ans;
    }
}
   

代码解释

这种方法确保了我们以最小的船数满足所有条件，同时处理了所有可能的边界情况。

转载地址：http://aaqo.baihongyu.com/