1.贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
1. 局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
2. for 控制 胃口，里面的 if 控制饼干。
3. 技巧：用了一个 index 来控制饼干数组的遍历，遍历饼干并没有再起一个 for 循环，而是采用自减的方式。
1 class Solution: 2 def findContentChildren(self, g, s): 3 g.sort() # 将孩子的贪心因子排序 4 s.sort() # 将饼干的尺寸排序 5 index = len(s) - 1 # 饼干数组的下标，从最后一个饼干开始 6 result = 0 # 满足孩子的数量 7 for i in range(len(g)-1, -1, -1): # 遍历胃口，从最后一个孩子开始 8 if index >= 0 and s[index] >= g[i]: # 遍历饼干 9 result += 1 10 index -= 1 11 return result
1. 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。
2. 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
3. 整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
4. 只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）
本题要考虑三种情况：
- 情况一：上下坡中有平坡
- 情况二：数组首尾两端
- 情况三：单调坡中有平坡
5. 也可以用动态规划进行求解。
1 class Solution: 2 def wiggleMaxLength(self, nums): 3 if len(nums) <= 1: 4 return len(nums) # 如果数组长度为0或1，则返回数组长度 5 curDiff = 0 # 当前一对元素的差值 6 preDiff = 0 # 前一对元素的差值 7 result = 1 # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值） 8 for i in range(len(nums) - 1): 9 curDiff = nums[i + 1] - nums[i] # 计算下一个元素与当前元素的差值 10 # 如果遇到一个峰值 11 if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0): 12 result += 1 # 峰值个数加1 13 preDiff = curDiff # 注意这里，只在摆动变化的时候更新preDiff 14 return result # 返回最长摆动子序列的长度