0881. 救生艇

0881. 救生艇 #

  • 标签:贪心、数组、双指针、排序
  • 难度:中等

题目大意 #

给定一个整数数组 people 代表每个人的体重,其中第 i 个人的体重为 people[i]。再给定一个整数 limit,代表每艘船可以承载的最大重量。每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit

要求:返回载到每一个人所需的最小船数(保证每个人都能被船载)。

解题思路 #

暴力枚举的时间复杂度为 $O(n^2)$。使用双指针可以减少循环内的时间复杂度。

我们可以利用贪心算法的思想,让最重的和最轻的人一起走。这样一只船就可以尽可能的带上两个人。

具体做法如下:

  • 先对数组进行升序排序,使用 ans 记录所需最小船数。
  • 使用两个指针 leftrightleft 指向数组开始位置,right 指向数组结束位置。
  • 判断 people[left]people[right] 加一起是否超重。
    • 如果 people[left] + people[right] > limit,则让重的人上船,船数量 + 1,令 right 左移,继续判断。
    • 如果 people[left] + people[right] <= limit,则两个人都上船,船数量 + 1,并令 left 右移,right 左移,继续判断。
  • 如果 lefft == right,则让最后一个人上船,船数量 + 1。并返回答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        size = len(people)
        left, right = 0, size - 1
        ans = 0
        while left < right:
            if people[left] + people[right] > limit:
                right -= 1
            else:
                left += 1
                right -= 1
            ans += 1
        if left == right:
            ans += 1
        return ans
本站总访问量  次  |  您是本站第  位访问者