881. 救生艇

逃离我推掉我的手 2022-09-08 14:48 113阅读 0赞

#### 2021-08-26 LeetCode每日一题 ####

链接：[https://leetcode-cn.com/problems/boats-to-save-people/][https_leetcode-cn.com_problems_boats-to-save-people]

标签：**贪心、排序、数组、双指针**

> 题目

第 i 个人的体重为 people\[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 <= 50000
 *  1 <= people\[i\] <= limit <= 30000

> 分析

题目规定每艘船最多载2人，并且所有人都要坐上船，求最少要几条船。

这种**最少**的问题，只要每次保证选择是最优解。这里就是每次尽量选择两个人坐船，这样最后就是最少数量。可以使用**排序 + 双指针**。

重量从小到大排完后，两边一起移动，如果两个体重和不大于limit，则说明两个人可以坐一条船，如果大于limit，则说明右边这个人只能坐一条船，因为左边的这个人是目前未上船的人中体重最小的，再也找不到比它更小的人了。

> 编码

class Solution { 
        public int numRescueBoats(int[] people, int limit) { 
            int res = 0, len = people.length;
            Arrays.sort(people);
            int left = 0, right = len - 1;
    
            while (left <= right) { 
                // 一艘船可以载两个人
                if (people[left] + people[right] <= limit) { 
                    res++;
                    left++;
                    right--;
                } else { 
                    // 和体重最小的都坐不下，则下标为right的单独坐一艘船
                    res++;
                    right--;
                }
            } 
    
            return res;
        }
    }

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]

[https_leetcode-cn.com_problems_boats-to-save-people]: https://leetcode-cn.com/problems/boats-to-save-people/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/31b2afa9b4fd47d3b1c64964badf8f85.png