一、题目

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

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

点击查看原题
难度级别： 中等

二、思路

1）贪心

由于每艘船最多可以同时载两个人，假设现在最瘦的人体重为min，最胖的人为max，有：

  • 如果min+max超重，那么max只能自己坐一艘船
  • 如果min+max没有超重，那么两人坐同一艘船

三、代码

1）贪心

  1. class Solution {
  2.     public int numRescueBoats(int[] people, int limit) {
  3.         Arrays.sort(people);
  4.         int s = 0, e = people.length - 1;
  5.         int ans = 0;
  6.         while (s < e) {
  7.             while (s < e && (people[s] + people[e]) > limit) {
  8.                 ans++;
  9.                 e--;
  10.             }
  11.             while (s < e && (people[s] + people[e]) <= limit) {
  12.                 ans++;
  13.                 s++;
  14.                 e--;
  15.             }
  16.         }
  17.         return s == e ? ans+1 : ans;
  18.     }
  19. }

时间复杂度为O(n)，空间复杂度为O(1)，这里不算上sort排序的时间和空间