881. 救生艇

August 26, 2021LeetCode

题目：881. 救生艇

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

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

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

刚开始读完题目在想是不是需要用动态规划？但我又不太会，那还是用回溯算法试试吧。等看完示例，思考一阵之后发现根本不用这么复杂。

首先根据题意每艘船最多只能乘坐两个人，然后题目问的是“最少多少个小船能坐下“，那么说明每人的体重都小于等于船的 limit。

那么，解题思路：首先给数组排序从大到小（从小到大也行）顺序，然后定义左右指针，数组两端的数值相加小于等于 limit 就乘坐两个人，反之就乘坐一个人。没错，这个中等的题就这么简单。

var numRescueBoats = function (people, limit) {
  people.sort((a, b) => b - a)
  let left = 0
  let right = people.length - 1
  let count = 0
  while (left <= right) {
    count++
    if (people[left] + people[right] <= limit) {
      right--
    }
    left++
  }
  return count
}