class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
}
};
881. 救生艇
给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
示例 1：
输入：people = [1,2], limit = 3 输出：1 解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3 输出：3 解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5 输出：4 解释：4 艘船分别载 (3), (3), (4), (5)
提示：
1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104原站题解
javascript 解法, 执行用时: 138 ms, 内存消耗: 57.2 MB, 提交时间: 2024-06-10 00:22:38
/**
* @param {number[]} people
* @param {number} limit
* @return {number}
*/
var numRescueBoats = function(people, limit) {
let ans = 0;
people.sort((a, b) => a - b);
let light = 0, heavy = people.length - 1;
while (light <= heavy) {
if (people[light] + people[heavy] <= limit) {
++light;
}
--heavy;
++ans;
}
return ans;
};
java 解法, 执行用时: 16 ms, 内存消耗: 52.2 MB, 提交时间: 2024-06-10 00:22:24
class Solution {
public int numRescueBoats(int[] people, int limit) {
int ans = 0;
Arrays.sort(people);
int light = 0, heavy = people.length - 1;
while (light <= heavy) {
if (people[light] + people[heavy] <= limit) {
++light;
}
--heavy;
++ans;
}
return ans;
}
}
cpp 解法, 执行用时: 65 ms, 内存消耗: 44.5 MB, 提交时间: 2024-06-10 00:22:11
class Solution {
public:
int numRescueBoats(vector<int> &people, int limit) {
int ans = 0;
sort(people.begin(), people.end());
int light = 0, heavy = people.size() - 1;
while (light <= heavy) {
if (people[light] + people[heavy] > limit) {
--heavy;
} else {
++light;
--heavy;
}
++ans;
}
return ans;
}
};
python3 解法, 执行用时: 91 ms, 内存消耗: 22.1 MB, 提交时间: 2024-06-10 00:21:52
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
ans = 0
people.sort()
light, heavy = 0, len(people) - 1
while light <= heavy:
if people[light] + people[heavy] > limit:
heavy -= 1
else:
light += 1
heavy -= 1
ans += 1
return ans
golang 解法, 执行用时: 92 ms, 内存消耗: 7.5 MB, 提交时间: 2021-08-26 14:24:32
func numRescueBoats(people []int, limit int) int {
sort.Ints(people)
low, high := 0, len(people) - 1
ans := 0
for low <= high {
if people[low] + people[high] <= limit {
low++
}
high--
ans++
}
return ans
}