一.题目描述

给定数组 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数组进行升序排序。排序后，数组左端为当前最轻人员的体重，右端为当前最重人员的体重，可快速定位两极体重，为后续双指针操作提供基础，避免盲目搭配导致的救生艇浪费（若不排序，无法高效找到可共乘的两人组合，可能出现多使用救生艇的情况）。
• 双指针定位：排序后，设置两个指针辅助搭配人员：左指针left初始指向数组起始位置（最轻人员），右指针right初始指向数组末尾位置（最重人员）；同时定义计数变量count，用于记录所需救生艇数量，初始值为0，确保每安排1艘救生艇就及时计数，避免遗漏或重复。
• 循环搭配逻辑（核心步骤）：以“left ≤ right”作为循环条件（确保所有人员都被安排），根据两人体重和与limit的关系，分两种情况处理，兼顾效率与正确性：
  （1）若people[left] + people[right] ≤ limit：说明当前最轻人员与最重人员可共乘1艘救生艇，此时两人均已安排完毕，left向右移动（指向次轻人员）、right向左移动（指向次重人员），同时count加1（记录1艘救生艇）；
  （2）若people[left] + people[right] > limit：说明最重人员无法与任何其他人员共乘（连最轻人员都无法搭配，更无法与其他体重更大的人员搭配），只能单独乘坐1艘救生艇，此时right向左移动（最重人员已安排），count加1（记录1艘救生艇）；
  （3）特殊情况补充：当left == right时，说明剩余1名人员未安排，单独安排1艘救生艇，count加1后循环结束，确保无人员遗漏。
• 思路验证与边界考量：为确保思路可行，结合示例和边界情况进一步验证，避免思路漏洞：
  （1）示例验证：以people = [3,2,2,1]、limit = 3为例，排序后为[1,2,2,3]，通过双指针循环搭配，最终得出需3艘救生艇，修正了初始思考中“需2艘”的错误，验证了思路的正确性；其他示例（如[1,2]、[1,1,1,1]）均能通过该思路得出正确结果。
  （2）边界情况考量：重点考虑4种极端场景，确保思路的完整性：① 人数为1时，直接返回1；② 所有人体重均等于limit时，每艘艇只能载1人，数量等于人数；③ 所有人体重均为limit/2（limit为偶数）时，每两人共乘1艘，数量为人数//2；④ 最轻与最重人体重和刚好等于limit时，实现最优搭配，最大化利用救生艇。

2.完整代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        if people is None:
            return 0
        people.sort()
        left=0
        right=len(people)-1
        count=0
        while(left<=right):
            if people[left] + people[right] <=limit:
                left=left+1
            right=right-1
            count+=1
        return count      
          

3.代码分析

• 排序语句：people.sort()——对应思路中的“排序铺垫”步骤。该语句对people数组进行原地升序排序，无需额外开辟空间（相较于sorted()函数，原地排序空间复杂度更低），排序后数组两端分别为最轻、最重体重，为后续双指针定位提供基础，避免盲目搭配，确保每一步搭配都能最大化利用救生艇承载能力。
• 初始化语句：left = 0、right = len(people) - 1、count = 0——对应思路中的“双指针定位”步骤。left指向数组起始位置（最轻人员），right指向数组末尾（最重人员），与思路中双指针的定义完全一致；count初始化为0，用于记录救生艇数量，确保每安排1艘救生艇及时计数，避免遗漏或重复，贴合思路中“计数变量”的核心作用。
• 循环逻辑语句：while left <= right:——循环条件与思路完全一致，确保所有人员都能被安排，覆盖“多人搭配”“单人剩余”等所有场景，避免出现人员遗漏的情况。
• 核心判断语句：if people[left] + people[right] <= limit:——对应思路中循环搭配的两种情况：
  ① 若条件成立：执行left =left+ 1，表示最轻人员与最重人员共乘1艘救生艇，两人均已安排完毕，left右移（指向次轻人员）、后续循环中right会自动左移（指向次重人员），与思路中“两人共乘，双指针同时移动”的逻辑完全匹配；
  ② 若条件不成立：不执行left移动，仅后续执行right =right-1，表示最重人员无法与任何人共乘，单独乘坐1艘救生艇，与思路中“最重人员单独乘坐，right左移”的逻辑一致。
• 计数与指针移动语句：right =right-1、count += 1——无论两人是否能共乘，每循环一次都对应1艘救生艇的使用（要么两人共乘1艘，要么最重人员单独1艘），因此每次循环都执行count加1、right左移，既简化了代码逻辑，又精准贴合思路中的搭配规则，避免了冗余判断。

4.复杂度分析

• 时间复杂度：核心耗时为排序操作，Python中sort()函数采用Timsort算法，时间复杂度为O(nlogn)；双指针循环操作的时间复杂度为O(n)（仅遍历数组一次），整体时间复杂度由排序决定，为O(nlogn)，效率较高，适用于大规模数组场景。
• 空间复杂度：采用原地排序（people.sort()），无需额外开辟数组空间，仅使用3个变量（left、right、count），空间复杂度为O(1)，相较于使用sorted()函数（空间复杂度O(n)），进一步优化了空间利用，符合算法高效性要求。

5.优缺点

优点：

• 空间复杂度为O（1），无需额外开辟数组空间，优化了空间利用
• 时间复杂度为O(nlogn)，排序操作是贪心思路的必要前提，无法进一步优化，双指针遍历仅需O(n)时间，整体效率可满足大规模数组场景，相较于暴力枚举（时间复杂度O(n²)），性能提升显著；

缺点 ：

• 排序操作不可避免：由于依赖排序实现双指针的高效搭配，无法摆脱O(nlogn)的时间复杂度，在极端场景（如数组已有序）下，排序操作会造成轻微的时间浪费；
• .原地排序会修改原数组：people.sort()为原地排序，会直接改变输入数组的元素顺序，若业务场景中要求保留原数组的原始顺序，需额外开辟空间存储原数组，会增加空间复杂度；