救生艇Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定数组 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 * 104
- 1 <= people[i] <= limit <= 3 * 104
# 思路
// 排序，然后看最重的能否跟最轻的一起走，如果可以，一起走，如果不行，单独走。 直觉上最重的不一定要跟最轻的一起走，应该跟一个“比较轻”的一起走，使得总和尽量大，但又不超过limit。
// 比如排序数组：{a1, a2, a3, a4}，假设a4 + a1 <= limit, a4 + a2 <= limit。
// 这时候a4最理想的应当是带走a2，而不是a1，尽量留最小的使得更容易跟a3一起走。但实际上，既然a1,a2都能跟a4一起走，而a4又大于a3，那么a3必定也能跟a1，a2一起走的。所以无须考虑这个层次，直接考虑最重的能否跟最轻的一起走即可。
# 解法
class Solution {
// 排序，然后看最重的能否跟最轻的一起走，如果可以，一起走，如果不行，单独走。 直觉上最重的不一定要跟最轻的一起走，应该跟一个“比较轻”的一起走，使得总和尽量大，但又不超过limit。
// 比如排序数组：{a1, a2, a3, a4}，假设a4 + a1 <= limit, a4 + a2 <= limit。
// 这时候a4最理想的应当是带走a2，而不是a1，尽量留最小的使得更容易跟a3一起走。但实际上，既然a1,a2都能跟a4一起走，而a4又大于a3，那么a3必定也能跟a1，a2一起走的。所以无须考虑这个层次，直接考虑最重的能否跟最轻的一起走即可。
public int numRescueBoats(int[] people, int limit) {
int res = 0;
int right = people.length - 1;
int left = 0;
Arrays.sort(people);
while (left <= right) {
if (left == right) {
res++; // 只剩下最后一个,直接一个走,结束
break;
}
if (people[left] + people[right] > limit) {
res++;
right--; // 先载最重的, 而且最小的也无法一起载,那么就最重的单独走
}
else {
res++;
right--; // 最重的与最轻的一起走
left++;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 总结
- 分析出几种情况，然后分别对各个情况实现
