LeetCode 881 Boats to Save People

思路

贪心+双指针。将数组排序后，两个指针分别指向最轻的和最重的两个人。如果二者之和超过limit，那么只能让最重的人上船；否则二人可上一艘船。

复杂度

时间复杂度O(n)

空间复杂度O(1)

代码

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int result = 0;
        int light = 0, heavy = people.length - 1;
        
        while (light <= heavy) {
            result++;
            if (people[light] + people[heavy] <= limit) {
                light++;
            }
            heavy--;
        }
        return result;
    }
}