任务

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

思路

对s和g排序，每次所能满足的最大胃口的孩子，计数。注意要从胃口开始倒序遍历，索引自然递减，而对于尺寸的递减，则通过index的形式，每用掉一个，递减，并且统计分配数量。
注意自然递减不能用尺寸，模拟一下可以发现

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        s.sort()
        g.sort()
        index = len(s)-1
        count = 0
        for i in range(len(g)-1,-1,-1): #这里必须遍历g而非s
            if index >=0 and g[i] <= s[index]:
                count += 1
                index -= 1
        return count

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

思路

本题很难想，最基础的思路是，用prevDiff和nextDiff记录当前的节点的前后diff，如果异号，则说明可以保留并且统计加1，即基础条件为if preDiff >0 and nextDiff < 0 or preDiff<0 and nextDiff > 0，然后遍历过程中prevDiff随着nextDiff修改

• 情况一： 首尾节点的处理，首节点，假装之前还有一个和他相等的节点，那么是否统计第一个节点只看和第二个节点的关系即nextDiff，为了统一逻辑，则上面的基础条件变为 if preDiff >= 0 and nextDiff < 0 or preDiff<=0 and nextDiff > 0
• 情况二： 非单调有平坡，可以延续情况一的逻辑
• 情况三： 单调有平坡，将修改时机从 遍历过程中prevDiff随着nextDiff修改 改为，只有发生方向变化时，才修改prevDiff，这个很难想到
  从看完题解再分析，可以分析思路是找到需要保留的节点，因为最终形成的是摆动序列，所以最终形成的prev,diff是只记录方向变化的

class Solution376:
    def wiggleMaxLength(self, nums: List[int]) -> int: 
        if len(nums) == 1: 
            return 1
        
        preDiff = 0
        nextDiff = 0
        result = 1 # 默认最后一个为一个波动
        
        for i in range(len(nums)-1):
            nextDiff = nums[i+1] - nums[i]
            if preDiff >= 0 and nextDiff < 0 or preDiff<=0 and nextDiff > 0:
                result +=1    
                preDiff = nextDiff # 只有方向改变时才修改prediff、
        return result

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

思路

暴力的解法是找到每一个索引为首的最大和连续子数组，复杂度为O(n^2)。
考虑动规的解法，dp[i]表示以当前索引i为结尾的最大子数组和，那么dp[i-1]表示以索引i-1为结尾的最大子数组和，dp[i]就取包含以i-1结尾的子序列和不包含以i-1结尾的子序列两种情况中的最大值，即dp[i] = max(dp[i-1]+nums[i],nums[i])

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums) # dp数组的元素： 以当前索引i结尾的最大和连续子数组的长度
        dp[0] = nums[0]
        
        for i in range(1,len(nums)):
            dp[i] = max(dp[i-1]+nums[i],nums[i])
        
        return max(dp)

贪心思路：当遍历到某个数和为负数时，则以下一个数为起点，重新累加

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = float("-inf")
        sum = 0 
        for i in range(len(nums)):
            sum += nums[i]
            result = sum if result<sum else result
            if sum < 0:
                sum = 0
        return result

心得体会

贪心法的思路非常灵活，且是用局部最优来尝试是否达到全局最优，其中的证明也是比较困难的，现阶段还无法严格证明，只能去模拟看是否可以通过，或无法举出反例的情况，可以锻炼一定的思维能力，想不出来可以看题解，看懂思路后编码即可，不必追求完美。本章的目标就是理解思路后的编码能力.