第二十七天：贪心算法part01（第八章）

1.分发饼干

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        #我的目标是尽可能满足可能多的孩子:尽量用最小的饼干满足最小胃口的孩子，这样大饼干可以留给更“难伺候”的孩子。
        g.sort()
        s.sort()

        Sum, cnt = 0, 0

        i, j = 0, 0  
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                i += 1 # 满足了一个孩子
            j += 1 # 用掉了一个饼干
        return i

 2.摆动序列

376. 摆动序列 - 力扣（LeetCode）

思路：

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        #删除单调坡上的元素
        #情况：1.有平坡
               #2.首尾元素：

        if len(nums) <= 1:
            return len(nums)
        curDiff = 0  #当前一对元素的差值
        preDiff = 0  #前一对元素的差值

        result = 1
        for i in range(len(nums) -1):
            curDiff = nums[i+1] - nums[i]  ## 计算下一个元素与当前元素的差值
            if(preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
                result += 1
                preDiff = curDiff # 注意这里，只在摆动变化的时候更新preDiff
        return result

3.最大子序和:

53. 最大子数组和 - 力扣（LeetCode）

 思路：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        #最大和的连续子数组
        #只要连续和不是负数，一直往后加
        Sum = 0
        result = float('-inf')
        for i in range(len(nums)):
            if Sum >= 0:
                Sum += nums[i]
                result = max(Sum, result)
            else:
                Sum = nums[i]
        return result