881-救生艇

暴力解只能解决一部分的case

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        cnt = 0  # 船的数量
        addSum = 0  # 累计和
        left = 0  # 左指针

        for right in range(len(people)):
            if people[left] == limit:
                cnt += 1
                if (right+1) < len(people):
                    left = right + 1
                addSum = 0
                print(str(right) + ': people[left] == limit')
            elif people[right] == limit:
                cnt += 2
                if (right+1) < len(people):
                    left = right + 1
                addSum = 0
                print(str(right) + ': people[right] == limit')
            else:
                addSum += people[right]
                if addSum >= limit:
                    print(str(right) + ': addSum')
                    cnt += 1
                    if addSum > limit:
                        left = right
                        addSum = people[right]
                    else:
                        if (right+1) < len(people):
                            left = right + 1
                        addSum = 0

        print(addSum)
        if addSum != 0:
            cnt += 1
        
        return cnt

WARNING：明显是一开始没有理解题意，题意是一艘船最多载两个人，而且不是一定要挨着的元素才能一起坐船，所以上面的代码一开始就错了

贪心算法（双指针）

=》sort之后+对撞指针

思路：如果重的胖子和最轻的瘦子不能一起坐船，那么最轻的瘦子就得跟第二胖匹配，如果匹配成功那就一起坐船走。

对撞双指针的结束条件是，当左指针下标大于右指针时，就要结束

知识点：

1. python的排序函数是啥？
   list.sort()

正确题解：

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        cnt = 0  # 船的数量
        left = 0  # 左指针
        right = len(people) - 1  # 右指针

        people.sort()
        # 而不是 left != right 
        while left <= right:
            if people[left] + people[right] <= limit:
                left += 1
            right -= 1
            cnt += 1
        
        return cnt