881. 救生艇
解题思路
题目意思进行模拟,则直接遍历数组,优先选择能够配对的两人,然后将这两人移除,重新配对。
但这样并不能保证一定是最优的,采用贪心的策略,要使船的数量尽可能少,应当使每一艘船载的人数尽可能多。
这样,先将人的重量排序,利用双指针进行计算。
C++
class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {sort(people.begin(), people.end());int res = 0;int left = 0, right = people.size() - 1;while(left <= right){if (people[left] + people[right] > limit){right--;}else{right--;left++;}res++;}return res;}
};
Python
class Solution:def numRescueBoats(self, people: List[int], limit: int) -> int:people.sort()res = 0left, right = 0, len(people)-1while left <= right:if people[left] + people[right] > limit:right -= 1else:right -= 1left += 1res += 1return res
Java
class Solution {public int numRescueBoats(int[] people, int limit) {int res = 0;Arrays.sort(people);int left = 0, right = people.length - 1;while (left <= right){if (people[left] + people[right] > limit){right--;}else {right--;left++;}res ++;}return res;}
}