局部最优 全局最优 局部最优可以推出全局最优 并且想不出反例
-----------------------------
(1) 455 分发饼干
(2) 376 摆动序列
(3) 122 买卖股票的最佳时机2
(4) 55 跳跃游戏
(3) 53 最大子序和
-----------------------------
一、简单题目
1、455 分发饼干
455. 分发饼干 - 力扣（LeetCode）
题目描述：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
--------------- python ---------------
class Solution:def findContentChildren(self, g, s):g.sort() # 将孩子的贪心因子排序s.sort() # 将饼干的尺寸排序index = len(s) - 1 # 饼干数组的下标，从最后一个饼干开始result = 0 # 满足孩子的数量for i in range(len(g)-1, -1, -1): # 遍历胃口，从最后一个孩子开始if index >= 0 and s[index] >= g[i]: # 遍历饼干result += 1index -= 1return result二、中等题目-序列问题
1、376 摆动序列
376. 摆动序列 - 力扣（LeetCode）
题目描述：给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
--------------- python ---------------
class Solution:def wiggleMaxLength(self, nums):if len(nums) <= 1:return len(nums) # 如果数组长度为0或1，则返回数组长度curDiff = 0 # 当前一对元素的差值preDiff = 0 # 前一对元素的差值result = 1 # 记录峰值的个数，初始为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 # 峰值个数加1preDiff = curDiff # 注意这里，只在摆动变化的时候更新preDiffreturn result # 返回最长摆动子序列的长度三、中等题目-贪心解决股票
1、122 买卖股票的最佳时机2
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
题目描述：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
Tips：只收集每天的正利润。
class Solution:def maxProfit(self, prices: List[int]) -> int:result = 0for i in range(1, len(prices)):result += max(prices[i] - prices[i - 1], 0)return result四、中等题目-两个维度权衡
五、有点难度-区间问题
1、55 跳跃游戏
55. 跳跃游戏 - 力扣（LeetCode）
题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
Tips：关注的是跳跃覆盖范围。
class Solution:def canJump(self, nums: List[int]) -> bool:cover = 0if len(nums) == 1: return Truei = 0# python不支持动态修改for循环中变量,使用while循环代替while i <= cover:cover = max(i + nums[i], cover)if cover >= len(nums) - 1: return Truei += 1return False六、有点难度-其他
1、53 最大子序和
53. 最大子数组和 - 力扣（LeetCode）
题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
--------------- python ---------------
class Solution:def maxSubArray(self, nums):result = float('-inf') # 初始化结果为负无穷大count = 0for i in range(len(nums)):count += nums[i]if count > result: # 取区间累计的最大值（相当于不断确定最大子序终止位置）result = countif count <= 0: # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和count = 0return result