漫画：贪心系列 之 救生艇的逃生

小浩算法改版了，大家看一下风格怎么样，还喜欢吗？所有的排版，绘图，文案，题解都是由小浩一人完成哦~

今天为大家分享一道关于“救生艇”的题目。

话不多说，直接看题。

01第881题：救生艇

第881题：第 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

（只要一瞪，就会了）

02题目分析

这不是一道算法题，这是一个脑筋急转弯。

一个船最多可以装两个人，并且不能把船压垮。同时要求把这些人可以统统装下的最小船数。用脚趾头也可以想到，我们需要尽最大努力的去维持一个床上得有两个人。。哦，不，船上。这是什么思想？Bingo，贪心。

思路很简单：

1. 我们首先需要让这些人根据体重进行排序。

2. 同时维护两个指针，每次让最重的一名上船，同时让最轻的也上船。（因为最重的要么和最轻的一起上船。要么就无法配对，只能自己占用一艘船的资源）

03JAVA示例

根据分析，得到代码：

 1//JAVA
 2class Solution {
 3    public int numRescueBoats(int[] people, int limit) {
 4        Arrays.sort(people);
 5        int i = 0, j = people.length - 1;
 6        int ans = 0;
 7
 8        while (i <= j) {
 9            ans++;
10            if (people[i] + people[j] <= limit)
11                i++;
12            j--;
13        }
14        return ans;
15    }
16}

04GO示例

GO代码其实也一样：

 1func numRescueans(people []int, limit int) int {
 2    sort.Ints(people)
 3    ans := 0
 4    i, j := 0, len(people)-1
 5    for i <= j {
 6        if people[i]+people[j] <= limit {
 7            i++
 8        }
 9        j--
10        ans++
11    }
12    return ans
13}

小浩申明

注：本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过相关语法。算法思想最重要，使用各语言纯属本人爱好。同时，所有代码均在leetcode上进行过测试运行，保证其严谨性！

05题目扩展

这里肯定马上就有细心的读者会问！为什么你每次是让最瘦的和最胖的来凑一对。而不是放弃掉这个最瘦的，去找一个逼近limit体重的人来乘船呢？这里要注意题目，因为题中已经告诉了， 一艘船仅能坐两人。所以去找一个逼近limit体重的人是没有意义的。

但是，这里并不妨碍我们将此题扩展进行思考。这里留下疑问，如果我们不对船上的人数进行限制，那么应该如何来完成本题呢？大家可以尝试代码练习一下。

评论区留下你的思路~

---

“要进学习群的小伙伴记得加我，和小浩做朋友”

长按左侧二维码

加小浩私人微信

（加我之前，

怎么得关注一下咯）

          关注领取

          “GEEKTIME”

          全部资源

发现了吗？近日小浩已经将所有的广告都关掉了！也就是说，所有的文章，对我一点收入都不会有。我唯一想要的，就是大家可以顺手帮我转发，足够我高兴一整天。这也是支持我一直写下去的动力。