求解思路

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

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

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

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

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

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

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public static int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int ans = 0;
    int l = 0;
    int r = people.length - 1;
    int sum = 0;
    while (l <= r) {
        sum = l == r ? people[l] : people[l] + people[r];
        if (sum > limit) {
            r--;
        } else {
            l++;
            r--;
        }
        ans++;
    }
    return ans;
}

举个栗子

假设 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 艘。

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

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