每日一题(21-08-26)题目881
原题:
第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/boats-to-save-people 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
先从题目获取关键的数据,最大重量limit、最多载两人、最小船数等。
最多载两人:要么一船一人,要么一船两人。
最大重量limit:一船的两人或一人重量不能超过limit。
最小船只:就是计算最小值,最小值的话就是尽量达成一船两人的条件。
思路:
根据以上信息可以想到尽量实现一船两人的情况,那么可以将最大值加最小值之和是否超过limit来判断。
因为people数组的数据不是有序的,那么可以先进行排序,这里进行从小到大排序,这样就方便最大最小值的获取。
计算过的值不应再继续用于计算,所以定义最小值指针(min)和最大值的指针(max)用于记录。
循环的前提是最大值指针大于等于最小值指针,小于的话就是已经所有数值遍历完了。
根据以上的条件和思路,实现代码如下:
class Solution {
public int numRescueBoats(int[] people, int limit) {
//2
Arrays.sort(people);
//3
int min = 0;
int max = people.length - 1;
//4
while (min <= max) {
//1
if (people[max] + people[min] <= limit) {
++min;
}
--max;
}
return people.length - 1 - max;
}
}