基本信息

  • 题号：881
  • 题厂：亚麻
  • 难度系数：中


数组 people：待救人员的体重

limit：救生船最大承重

每艘船只能装 2 个人，问要最少派多少艘船可以把人全部救回……

例如：people = [1,2], limit = 3

只需派一艘船装 2 人即可：1 + 2 = 3

解题思路

题目限制个人体重最大值 大于等于 limit 上限

  • 如果个人体重刚好等于 limit 上线，无需配对；2 人搭船配对的情况只发生在 2 人体重都小于 limit 上限且 2 人体重相加也不超标……
  • 为了让派出船的数量最小，2 人搭船配对时要尽量接近上限值不要浪费。例如 limit 为 10，9 + 1 = 10；4 + 6 = 10 不造成浪费；而 1 + 4 配对将造成 9 + 6 超标需要多派一艘船……于是著名的贪心算法闪亮登场了……
  • 怎么才能 9 + 1 完美配对？可以考虑先将数组进行排序，再按照双指针逻辑相向而行……
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        
        res = 0 # 船只初始数量
        l, r = 0, len(people) - 1
        
        # 右指针每移动一格，就派出一艘船……
        # 如果左指针刚好可以和右指针配对，左指针也跟着移动一格……直到左右指针相遇为止……
        while l <= r:
            remain = limit - people[r]
            r -= 1
            res += 1
            
            if l <= r and remain >= people[l]:
                l += 1
                
        return res

Constraints

  • 1 <= people.length <= 5 * 104
  • 1 <= people[i] <= limit <= 3 * 104

个人体重最大限就是等于 limit 上限，即一人独享一艘船。考试时，要向考官咨询问清楚……


Big O

  • Time：O（nlog n），双指针虽然复杂度为 O（n），但用了排序，所以时间复杂度以最高额度计算……
  • Space：O（1）


测试

  • 当只有一个人时
  • 当混合时……


总结

  • 本题虽然代码简单，但需要运用到略高级的贪心算法，应该划归中档偏难
  • 除了熟练掌握双指针，还要在理解题意后反应到需要运用贪心算法解决问题……
  • 本题可作为贪心算法入门题定期复习……🙈