一、贪心算法

核心理念是每一步都做出局部最优选择，以期最终得到全局最优解。它通常用于求解一些最优化问题，例如最小生成树、最短路径、背包问题等。

二、贪心算法的步骤

1. 定义选择标准：确定每一步如何选择当前最优解。

2. 验证贪心策略的正确性：分析问题是否满足贪心算法的条件，确保贪心选择可以得到最优解。

3. 迭代选择：从初始状态开始，每一步按照选择标准做出决策，直到找到问题的完整解决方案。

三、贪心算法的优缺点

优点：

• 简单且高效：贪心算法通常实现简单，运行速度较快。

• 适用性强：适用于许多最优化问题，例如图算法中的最小生成树和最短路径。

缺点：

• 不保证全局最优解：并非所有问题都能通过贪心算法获得最优解。尤其是涉及多个约束条件的复杂问题，贪心选择可能导致非最优解。

• 适用场景有限：只有当问题满足最优子结构和无后效性时，贪心算法才能得到全局最优解。

455. 分发饼干

解题思路：需要找出有几个满足饼干>小孩，尽量用大的饼干满足较大的小孩

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int: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 -= 1  # 使用掉一个饼干，向前移动return result

解题思路：就从小到大尝试，满足则把小孩的index+1，最后返回index

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

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。

解题思路：保留峰值，把单调坡上的中间元素删除

计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。

本题要考虑三种情况：

1. 情况一：上下坡中有平坡
2. 情况二：数组首尾两端
3. 情况三：单调坡中有平坡

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:if len(nums) <= 1: return len(nums)curDiff, preDiff = 0, 0result = 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 = curDiffreturn result

53. 最大子数组和

暴力递归

class Solution:def maxSubArray(self, nums: List[int]) -> int:result = float('-inf')count = 0for i in range(len(nums)):count = 0for j in range(i, len(nums)):count += nums[j]result = max(result, count)return result

贪心：遇到和为负数时，就重置，重新开始计算下个区间和

class Solution:def maxSubArray(self, nums: List[int]) -> int:max_sum = nums[0]current_sum = 0for num in nums:if current_sum < 0:current_sum = 0current_sum += nummax_sum = max(current_sum, max_sum)return max_sum