881.救生艇[中等]

題目：

給定數組?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 * 10**4
• 1 <= people[i] <= limit <= 3 * 10**4

?題目分析：

????????一艘船最多上兩個人，要使船只最少那就只能讓每只船載人盡可能多，那么最多就是兩個人，這里對people數組進行排序(假設從小到大排)，然后定義雙指針分別指頭和尾。判斷頭+尾是否大于limit:

• 大于的話則說明尾指針指向的最大值只能單獨乘船，此時應單獨分配一艘船給體重最重的人。從 people中去掉體重最重的人后，我們縮小了問題的規(guī)模，變成求解剩余 n?1 個人所需的最小船數，將其加一即為原問題的答案，此時尾指針向前走，船只加一；
• 否則則說明 頭 可以和 尾? 一起乘船，那么頭也能與其余任何人同乘一艘船，為了盡可能地利用船的承載重量，選擇與體重最重的人同乘一艘船是最優(yōu)的。從 people 中去掉體重最輕和體重最重的人后，就縮小了問題的規(guī)模，變成求解剩余 n?2 個人所需的最小船數，將其加一即為原問題的答案。此時頭尾都往中間走一步，船只加1。以此類推，遍歷一遍過去即可出答案。

代碼實現(xiàn)：

class Solution:def numRescueBoats(self, people: List[int], limit: int) -> int:people.sort()n=len(people)if n==1: return 1res=0st,ed=0,n-1while st<=ed:if people[st]+people[ed]<=limit:res+=1st+=1ed-=1else:res+=1ed-=1return res

總結：

???????代碼的邏輯是基于貪心算法，每次盡可能多地安排乘客乘坐救生艇達到最少的船只數，最后返回res即為所需的最少船只數。具體步驟如下：

1. 首先對乘客的重量列表進行排序，這樣可以從小到大依次選擇乘客。
2. 使用雙指針st和ed分別指向排序后的乘客列表的第一個和最后一個元素。
3. 如果st指向的乘客和ed指向的乘客的重量之和不超過limit，則表示可以安排這兩個乘客乘坐一艘救生艇，此時res加1，同時移動st和ed指針繼續(xù)判斷下一組乘客。
4. 如果st指向的乘客和ed指向的乘客的重量之和超過limit，則只能讓ed指向的乘客單獨乘坐一艘救生艇，此時res加1，移動ed指針繼續(xù)判斷。