难度: Medium
给定数组 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 * 1041 <= people[i] <= limit <= 3 * 104运行时间: 72 ms
内存: 22.3 MB
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
count=[0]*(limit+1) # count[i]=c 表示people[]中有且只有c个体重为i的人。
for w in people:
count[w]+=1
ans = len(people) # 先假定所有人独自乘船
l,r=1,limit-1 # 双指针表示体重
while l<r:
while l<r and 0==count[l]:l+=1 # 跳过不存在的体重
r=min(r,limit-l) # 保证 l+r <= limit
while l<r and 0==count[r]:r-=1 # 跳过不存在的体重
if l>=r:break
if count[l]>=count[r]:
count[l]-=count[r]
ans -= count[r]
r-=1
else:
count[r]-=count[l]
ans -= count[l]
l+=1
return ans-(count[l]//2 if l*2<=limit else 0) # 特别注意体重为l的人可以成对同乘一艘船的情况
此题解采用了计数排序和双指针技术来解决问题。首先，创建一个计数数组来存储每个可能的体重值的人数。然后初始化答案为人数总和，假设每个人都单独乘坐一艘船。使用双指针技术，一个指针从最轻的体重开始，另一个从最重的体重开始，尝试将两个体重的人配对乘坐同一艘船。如果可以配对，则减少相应的人数和所需的船数。当两个指针相遇时，停止配对，并检查最后剩余的同体重人是否可以成对乘坐。
时间复杂度: O(n + limit)
空间复杂度: O(limit)
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
count = [0] * (limit + 1) # 创建计数数组，存储每个体重的人数
for w in people:
count[w] += 1 # 填充计数数组
ans = len(people) # 初始假设每人独自一船
l, r = 1, limit - 1 # 设置双指针，分别指向最轻和最重
while l < r:
while l < r and count[l] == 0: l += 1 # 找到下一个有人的最轻体重
r = min(r, limit - l) # 确保两人体重之和不超过limit
while l < r and count[r] == 0: r -= 1 # 找到下一个有人的最重体重
if l >= r: break # 如果指针重合或交叉，停止配对
if count[l] >= count[r]:
count[l] -= count[r] # 配对并减少相应的人数
ans -= count[r] # 减少船数
r -= 1
else:
count[r] -= count[l]
ans -= count[l]
l += 1
return ans - (count[l] // 2 if l * 2 <= limit else 0) # 处理剩余同体重人是否可以成对乘船
计数排序特别适用于当输入的数据范围（即体重范围）不是很大时，它的时间复杂度可以达到O(n+k)，其中n是数组长度，k是数据的范围。由于体重的最大值限制为`limit`，使得计数排序的空间和时间效率非常高。此外，计数排序可以直接提供每个体重的人数，便于执行后续的双指针配对操作。
在双指针策略中，右指针`r`表示当前考虑的最重的体重，而左指针`l`表示最轻的体重。为了确保两人的总体重不超过`limit`，我们在配对前首先将右指针调整为`min(r, limit - l)`，这样可以保证即使最重的与最轻的人配对，其体重之和也不会超过`limit`。
当两个指针的体重之和恰好等于`limit`时，可以直接将这两个体重的人数对应减少，并且减少总需要的船数。然后根据消耗的人数更新左右指针，即如果左侧体重的人数不小于右侧体重的人数，则减少右侧体重的人数并左移右指针；反之，则减少左侧体重的人数并右移左指针。
当双指针相遇时，意味着所有可能的体重组合已经尝试过配对。此时，剩余的同体重的人（若有）可以继续尝试是否可以两两配对。由于没有其他不同的体重可以配对，进一步的配对只能在相同体重的人中进行，这也是为什么要检查剩余相同体重人的配对情况。因此，双指针相遇时停止配对是有效且必要的，它确保了所有不同体重的配对机会都已经被尽可能利用。