881.救生艇

【LetMeFly】881.救生艇：排序+双指针（大人掌船，能捎就捎）

力扣题目链接：https://leetcode.cn/problems/boats-to-save-people/

给定数组 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

解题方法：排序+双指针

具体做法

首先对所有人按体重从低到高排序。

使用两个指针$l$和$r$分别指向数组的第一个和最后一个元素。

每次$r$指针向前移动一个元素（并且救生艇数量加一），另外的，若$r$指针移动前$people[l]+people[r]\leq lmit$，则$l$指针右移一个元素（相当于大人捎个小孩）。

为什么这么做

为什么r指针每次都移动而l指针不一定移动？

反正每个人都得坐船走，可以理解为先分配大人（每次r左移），若此大人还能捎带一个小孩儿，则就把这个小孩儿带走（此时l右移）。

大人不应该带上“尽可能重的小孩”吗？

第一反应是这样的。对于大人$people[r]$，是否应该带上满足$people[i]+people[r]\leq limit$的最大$i$而不是剩下所有小孩中最小的$l$呢？

其实带谁都一样。反正都是一个人头。此时$r$能带上“更重的小孩$i$”，那么待会儿“更轻的大人”也一定能带上小孩$i$。带$l$写起来简单，所以带$l$不带$i$。

时空复杂度分析

• 时间复杂度$O(n\log n)$，其中$n=len(people)$
• 空间复杂度$O(\log n)$

时空复杂度的来源主要是排序。

AC代码

C++

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int ans = 0;
        for (int l = 0, r = people.size() - 1; l <= r; ans++, r--) {
            // 不用特判l是否等于r，因为不影响结果（若l=r则说明就剩一个人了，带不带那个“虚空影子”都无所谓）
            if (people[l] + people[r] <= limit) {
                l++;
            }
        }
        return ans;
    }
};

Go

// package main

// import "sort"

func numRescueBoats(people []int, limit int) int {
    sort.Ints(people);
    ans := 0
    for l, r := 0, len(people) - 1; l <= r; ans, r = ans + 1, r - 1 {
        if people[l] + people[r] <= limit {
            l++;
        }
    }
    return ans
}

Java

// import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int ans = 0;
        for (int l = 0, r = people.length - 1; l <= r; ans++, r--) {
            if (people[l] + people[r] <= limit) {
                l++;
            }
        }
        return ans;
    }
}

Python

# from typing import List

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        ans = 0
        l, r = 0, len(people) - 1
        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1
            r -= 1
            ans += 1
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139582336