881. 救生艇

思路

每艘船最多裝兩個人，一艘船能乘載的重量為limit，問最少需要幾艘船乘載所有人。 在排序數組之後，利用雙指針把最重的跟最輕的人配對。

• 如果最輕 + 最重的人 $\leq limit$，兩人共用一艘船
• 如果最輕 + 最重的人 $>limit$，最重的自己搭船，因為沒有更輕的人了。

程式碼

雙指針

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n = people.size();
        ranges::sort(people);
        int left = 0, right = n - 1;
        int res = 0;
        while(left <= right) {
            if(people[left] + people[right] <= limit) { // 最輕 + 最重 <= limit
                left++; // 移動左指針，以及右指針
            }
            // 無論哪種情況，最重的人都會搭到船。
            right--;
            res++;
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$