Loading... > https://leetcode.cn/problems/boats-to-save-people/description/?envType=daily-question&envId=2024-05-02 每艘船最多可以载两个人。要找到承载所有人所需的最小船数,可以用贪心的思想,让载两个人的船尽可能多。 因此这里可以将人的体重排序,然后使用双指针从两头向中间搜索。如果两个人的体重之和小于 `limit` ,则两个人都上船;反之则只让体重大的人单独上船,因为体重大的已经没有可以和他配对的人了。 ```c++ class Solution { public: int numRescueBoats(std::vector<int>& people, int limit) { const int n = people.size(); std::sort(people.begin(), people.end()); int left = 0, right = n - 1, res = 0; while (left < right) { if (people[left] + people[right] <= limit) { left++, right--; } else { right--; } res++; } if (left == right) res++; return res; } }; ``` - 时间复杂度:$O(nlogn)$ ,其中 $n$ 为 `people` 的数量。 - 空间复杂度:$O(logn)$ ,排序需要 $O(logn)$ 的额外空间。 最后修改:2024 年 06 月 12 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏