代码随想录算法训练营Day27

贪心算法【Greedy Algorithm】
力扣454.分发饼干【easy】
力扣376.摆动序列【medium】
力扣53.最大子数组和【medium】

一、贪心算法【Greedy Algorithm】

贪心算法的核心特征

• 局部最优选择：在每一步决策时，只考虑当前状态下最好的选择，不考虑未来的影响。
• 无回溯：一旦做出选择，就不再回头重新考虑（即没有“撤销”操作）。
• 高效性：通常时间复杂度较低，适合处理大规模问题。
  

适用

• 最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
• 贪心算法不一定能得到全局最优解，但当问题满足以下两个性质时，贪心策略可以保证全局最优：
  • 贪心选择性质（Greedy Choice Property）：通过局部最优选择能逐步构造出全局最优解。
  • 最优子结构（Optimal Substructure）：问题的最优解包含其子问题的最优解。

解题步骤：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解
• 做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

时间复杂度

• 时间复杂度通常较低：$O(n)orO(nlogn)$

何时使用？

• 问题具有明确的贪心选择性质（如“每次选最大/最小的元素”）。
• 需要快速得到一个近似最优解（即使不是严格最优）。
• 动态规划的时间复杂度不可接受时。

二、力扣454.分发饼干【easy】

题目链接：力扣

视频链接：代码随想录

1、思路

• 把 g 和 s 从小到大排序。
• 遍历饼干大小 s。同时维护另一个指针 i=0 表示胃口。
• 设 g 的长度为 n，如果 i<n and g[i]≤x，那么把饼干分给这个孩子，i += 1。
• i 增加的次数就是得到饼干的孩子个数，所以最后返回 i。
• 时间复杂度：$O(nlogn+mlogm)$

2、代码

• 遍历饼干，以小饼干优先

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()i = 0n = len(g)for x in s:if i < n and g[i] <= x:i += 1return i

• 遍历小孩的胃口，以大饼干优先

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort() index = len(s) - 1result = 0# 遍历小孩的胃口，以大饼干优先for i in range(len(g) - 1, -1, -1):if index >= 0 and g[i] <= s[index]:index -= 1result += 1return result

---

三、力扣376.摆动序列【medium】

题目链接：力扣376.摆动序列


视频链接：代码随想录

1、思路

• 这是我们思考本题的一个大体思路，但本题要考虑三种情况：
  • 情况一：上下坡中有平坡
  • 情况二：数组首尾两端
  • 情况三：单调坡中有平坡
• 情况一：上下坡中有平坡
  
• 情况二：首尾元素
  
• 情况三：单调有平坡

• 时间复杂度：$O(n)$

2、代码

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums) # 如果数组长度为0或1，则返回数组长度prediff = 0curdiff = 0result = 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 += 1prediff = curdiff # 注意这里，只在摆动变化的时候更新preDiffreturn result # 注意这里，只在摆动变化的时候更新preDiff

---

四、力扣53.最大子数组和【medium】

题目链接：力扣53.最大子数组和

视频链接：代码随想录

1、思路

• 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
• 全局最优：选取最大“连续和”
• 时间复杂度：$O(n)$

2、代码

class Solution:def maxSubArray(self, nums: List[int]) -> int:result = float('-inf') # 初始化结果为负无穷大count = 0for i in range(len(nums)):count += nums[i]if count >= result:result = countif count < 0:count = 0 # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和return result

---