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;
    }
}