第 13 课：贪心算法（Greedy）—— 最简单但最考验智慧的算法思想

这是第一个算法思想类的内容，和之前学的数据结构不同：数据结构解决 "怎么存数据" 的问题，算法思想解决 "怎么解决问题" 的问题。

贪心算法是所有算法思想中最简单、最直观的一个，但也是最考验智慧的一个 —— 它的代码往往只有几行，但你需要证明 "为什么贪心是对的"。

一、先想明白：为什么要有贪心算法？

我们先看一个生活中最常见的问题：

你有面值为 1 元、5 元、10 元、20 元的硬币，现在要找给别人 36 元，怎么找才能用最少的硬币数量？

所有人都会下意识地这么做：

1. 先拿 1 张 20 元（最大面值）
2. 再拿 1 张 10 元
3. 再拿 1 张 5 元
4. 最后拿 1 张 1 元总共 4 枚硬币，这确实是最优解。

你在做这个决定的时候，并没有考虑所有可能的组合（动态规划的思路），而是每一步都选择当前看来最好的选择—— 这就是贪心算法。

贪心算法的诞生，就是为了用最简单、最高效的方式，解决那些满足 "贪心选择性质" 的最优问题。它的时间复杂度通常是 O (n) 或 O (nlogn)，远低于动态规划的 O (n²)。

二、贪心算法的本质：局部最优推导出全局最优

✅ 核心思想（刻在脑子里）

每一步都做出当前看来最好的选择，并且希望通过这些局部最优的选择，最终得到全局最优的解。

两个必要条件（缺一不可）

只有同时满足以下两个条件的问题，才能用贪心算法解决：

1. 最优子结构性质：问题的最优解包含其子问题的最优解
2. 贪心选择性质：全局最优解可以通过一系列局部最优的选择得到

⚠️ 非常重要：贪心算法不是万能的。绝大多数问题都不满足贪心选择性质，这时候贪心只能得到近似解，不能得到全局最优解。

最经典的反例：

如果硬币面值是 1 元、3 元、4 元，要找 6 元。贪心算法会选：4 元 + 1 元 + 1 元（3 枚）但最优解是：3 元 + 3 元（2 枚）

这就是为什么贪心算法考验智慧 —— 你需要先判断问题是否满足贪心选择性质，再决定是否使用贪心。

三、贪心算法的解题步骤

1. 分解问题：把原问题分解成若干个相互独立的子问题
2. 贪心选择：对每个子问题，做出当前看来最好的选择
3. 合并结果：把所有子问题的解合并起来，得到原问题的解

四、经典例题（必做）

例题 1：LeetCode 455. 分发饼干（贪心入门必做）

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

核心思路：

• 把孩子的胃口从小到大排序
• 把饼干的尺寸从小到大排序
• 用最小的饼干，满足胃口最小的孩子
• 这样就能用最少的饼干，满足最多的孩子

为什么贪心是对的？因为如果有一个更小的饼干能满足这个孩子，那么用更大的饼干来满足他就是浪费。把更大的饼干留给胃口更大的孩子，才能满足更多的孩子。

代码

python

运行

def findContentChildren(g, s): """ 计算最多能满足多少个孩子 参数: g (List[int]): 孩子的胃口值列表 s (List[int]): 饼干的尺寸列表 返回: int: 能满足的最大孩子数量 """ # 将孩子的胃口从小到大排序 g.sort() # 将饼干的尺寸从小到大排序 s.sort() child = 0 # 指向当前要满足的孩子 cookie = 0 # 指向当前的饼干 # 遍历所有饼干和孩子 while child < len(g) and cookie < len(s): # 如果当前饼干能满足当前孩子 if s[cookie] >= g[child]: child += 1 # 满足一个孩子，指针后移 cookie += 1 # 无论是否满足，都尝试下一块饼干 return child # 返回满足的孩子总数 # 示例1 g1 = [1, 2, 3] # 三个孩子的胃口值 s1 = [1, 1] # 两块饼干的尺寸 result1 = findContentChildren(g1, s1) print(f"示例1: 孩子胃口={g1}, 饼干尺寸={s1}, 最多满足 {result1} 个孩子") # 应输出1 # 示例2 g2 = [1, 2] # 两个孩子的胃口值 s2 = [1, 2, 3] # 三块饼干的尺寸 result2 = findContentChildren(g2, s2) print(f"示例2: 孩子胃口={g2}, 饼干尺寸={s2}, 最多满足 {result2} 个孩子") # 应输出2 # 示例3 g3 = [10, 9, 8, 7] # 四个孩子的胃口值 s3 = [5, 6, 7, 8] # 四块饼干的尺寸 result3 = findContentChildren(g3, s3) print(f"示例3: 孩子胃口={g3}, 饼干尺寸={s3}, 最多满足 {result3} 个孩子") # 应输出2 # 示例4 g4 = [2, 3, 4] # 三个孩子的胃口值 s4 = [1, 2, 3, 4] # 四块饼干的尺寸 result4 = findContentChildren(g4, s4) print(f"示例4: 孩子胃口={g4}, 饼干尺寸={s4}, 最多满足 {result4} 个孩子") # 应输出3

例题 2：LeetCode 122. 买卖股票的最佳时机 II

题目：给你一个整数数组prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和 / 或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。

核心思路：只要后一天的价格比前一天高，我们就买入前一天的股票，卖出后一天的股票，赚取差价。把所有正的差价加起来，就是最大利润。

为什么贪心是对的？因为利润是可以拆分的。比如从第 1 天到第 3 天，价格从 1 涨到 3，利润是 2。这和第 1 天买第 2 天卖（利润 1），第 2 天买第 3 天卖（利润 1），总利润是一样的。

代码

python

运行

def maxProfit(prices): """ 计算买卖股票的最大利润 参数: prices (List[int]): 股票每天的价格列表 返回: int: 最大利润 """ profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit # 示例1 prices1 = [7, 1, 5, 3, 6, 4] result1 = maxProfit(prices1) print(f"示例1: 股票价格={prices1}, 最大利润={result1}") # 示例2 prices2 = [1, 2, 3, 4, 5] result2 = maxProfit(prices2) print(f"示例2: 股票价格={prices2}, 最大利润={result2}") # 示例3 prices3 = [7, 6, 4, 3, 1] result3 = maxProfit(prices3) print(f"示例3: 股票价格={prices3}, 最大利润={result3}")

✅ 这道题的代码只有 5 行，但很多人想破头都想不出来，这就是贪心算法的魅力。

例题 3：LeetCode 55. 跳跃游戏

题目：给定一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

核心思路：维护一个变量max_reach，表示当前能到达的最远位置。遍历数组中的每个位置，如果当前位置在max_reach范围内，就更新max_reach为max(max_reach, i + nums[i])。如果max_reach大于等于最后一个下标，说明可以到达，返回 True。

代码

python

运行

def canJump(nums): """ 判断是否能够到达数组的最后一个下标 参数: nums (List[int]): 非负整数数组，表示在每个位置可以跳跃的最大长度 返回: bool: 是否能够到达最后一个下标 """ max_reach = 0 for i in range(len(nums)): # 如果当前位置超出当前能到达的最远位置，无法继续前进 if i > max_reach: return False # 更新当前能到达的最远位置 max_reach = max(max_reach, i + nums[i]) # 如果已经可以到达或超过最后一个下标，返回True if max_reach >= len(nums) - 1: return True return False # 示例测试 if __name__ == "__main__": # 示例1: 能够到达最后一个下标 nums1 = [2, 3, 1, 1, 4] print(f"示例1: nums={nums1}, 是否能到达最后一个下标: {canJump(nums1)}") # 示例2: 无法到达最后一个下标 nums2 = [3, 2, 1, 0, 4] print(f"示例2: nums={nums2}, 是否能到达最后一个下标: {canJump(nums2)}") # 示例3: 每个位置只能跳1步，但能到达 nums3 = [1, 1, 1, 1, 1] print(f"示例3: nums={nums3}, 是否能到达最后一个下标: {canJump(nums3)}") # 示例4: 第一个位置就能跳到末尾 nums4 = [5, 4, 3, 2, 1] print(f"示例4: nums={nums4}, 是否能到达最后一个下标: {canJump(nums4)}") # 示例5: 起始位置为0，无法移动 nums5 = [0, 2, 3] print(f"示例5: nums={nums5}, 是否能到达最后一个下标: {canJump(nums5)}")

五、贪心算法的优缺点

优点

1. 简单直观：代码通常非常短，容易理解和实现
2. 效率极高：时间复杂度通常是 O (n) 或 O (nlogn)
3. 空间复杂度低：通常只需要常数级别的额外空间

缺点

1. 适用范围窄：只有少数问题满足贪心选择性质
2. 难以证明：证明贪心算法的正确性往往比写代码更难

六、贪心 vs 动态规划

表格

✅ 记住：能用贪心解决的问题，一定能用动态规划解决；但能用动态规划解决的问题，不一定能用贪心解决。