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)

题解

class Solution {
   public int numRescueBoats(int[] people, int limit) {
       // 核心思路：贪心算法 + 双指针
   // 1. 【排序】：
   //    首先对体重进行排序，目的是为了方便找到当前“最重”和“最轻”的人。

   // 2. 【贪心策略 - 无论如何，最重的人先上船】：
   //    我们每次都优先考虑当前最重的人（people[right]）。
   //    为了让船的利用率最高，我们尝试让他“带上”当前最轻的人（people[left]）。

   // 3. 【判断逻辑】：
   //    让最重的人（right）和最轻的人（left）一起上称：
   //    - 情况 A (people[left] + people[right] <= limit)：
   //      两人能坐同一艘船。于是皆大欢喜，两人都离开（left++, right--），船数+1。
   //    - 情况 B (people[left] + people[right] > limit)：
   //      最重的人太重了，连最轻的人都带不动。
   //      这就意味着这个最重的人无法和任何人拼船（因为连最轻的都不行，其他人更不行）。
   //      所以，最重的人只能独自坐一艘船离开（right--），船数+1。

   // 4. 【结论】：
   //    无论是一起走还是独自走，每一次循环都消耗一艘船（count++）。
       Arrays.sort(people);
       int left=0,right=people.length - 1,count = 0;
       while(left<=right){
           if(people[left]+people[right]<=limit){
               count++;
               left++;
               right--;
           }
           else{
               count++;
               right--;
           }
       }
       return count;
   }
}