核心算法 / 08
贪心算法
核心思想： 每步选局部最优，期望达到全局最优。
什么是贪心
贪心算法（Greedy Algorithm）的思路非常直觉化：在每一步决策时，都选择当前看起来最好的选项，不回头、不犹豫。如果问题本身具有特殊性质，这种”只看眼前”的策略最终就能得到全局最优解。
贪心 vs 动态规划
| 对比项 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 每步只选当前最优，不回头 | 考虑所有可能的子问题组合 |
| 时间复杂度 | 通常更低 | 通常更高 |
| 适用条件 | 需要贪心选择性质 | 只需最优子结构 |
| 实现难度 | 代码简单，难在证明正确性 | 代码稍复杂，难在状态定义 |
什么时候能用贪心
需要同时满足两个性质：
- 贪心选择性质：局部最优选择能导出全局最优。
- 最优子结构：问题的最优解包含子问题的最优解。
简单说就是——”每一步选最好的，最后结果也是最好的”。如果你发现某个问题”只看眼前”会漏掉更优解，那就该考虑 DP 或回溯了。
贪心的解题思路
- 将问题分解为子问题——明确每一步要做什么决策。
- 找到贪心策略——通常需要先排序，然后按某种规则逐个处理。
- 证明正确性——面试中简要说明”为什么局部最优能推出全局最优”即可，不需要严格数学证明。
贪心题的套路：排序 + 扫描 + 维护一个关键变量。
经典题目详解
跳跃游戏（LC 55）
题意：数组中每个元素表示你在该位置能跳的最大长度，判断能否到达最后一个位置。
贪心思路：从左到右遍历，维护一个”最远可达位置” max_reach。如果当前位置超过了 max_reach，说明到不了这里，直接返回 False。
def canJump(nums: list[int]) -> bool:
max_reach = 0 # 当前能到达的最远位置
for i, jump in enumerate(nums):
if i > max_reach:
# 当前位置已经超出可达范围，走不到这里
return False
max_reach = max(max_reach, i + jump)
return True
- 时间复杂度：O(n)
- 空间复杂度：O(1)
跳跃游戏 II（LC 45）
题意：保证能到达终点，求最少跳跃次数。
贪心思路：把每一跳能覆盖的范围看作一个”层”，类似 BFS 的层序遍历。每次都跳到能让下一层覆盖最远的位置。
def jump(nums: list[int]) -> int:
jumps = 0 # 跳跃次数
cur_end = 0 # 当前这一跳能覆盖的右边界
max_reach = 0 # 在当前层中能达到的最远位置
for i in range(len(nums) - 1):
max_reach = max(max_reach, i + nums[i])
if i == cur_end:
# 到达当前层的边界，必须跳一次
jumps += 1
cur_end = max_reach
return jumps
- 时间复杂度：O(n)
- 空间复杂度：O(1)
买卖股票的最佳时机 II（LC 122）
题意：可以多次买卖股票（但同一时间最多持有一股），求最大利润。
贪心思路：只要明天比今天贵，就今天买、明天卖。把所有上涨的差价都吃掉。
def maxProfit(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
- 时间复杂度：O(n)
- 空间复杂度：O(1)
分发饼干（LC 455）
题意：每个孩子有一个胃口值 g[i]，每块饼干有大小 s[j]。饼干 j 能满足孩子 i 当且仅当 s[j] >= g[i]。求最多能满足几个孩子。
贪心思路：排序后，用最小的饼干去满足胃口最小的孩子，尽量不浪费大饼干。
def findContentChildren(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
- 时间复杂度：O(n log n)，瓶颈在排序
- 空间复杂度：O(1)（原地排序）
合并区间（LC 56）
题意：给定若干区间，合并所有重叠的区间。
贪心思路：按左端点排序后，依次检查当前区间是否和上一个区间重叠。重叠就合并（取右端点的较大值），不重叠就直接加入结果。
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0]) # 按左端点排序
merged = []
for interval in intervals:
if merged and interval[0] <= merged[-1][1]:
# 与上一个区间重叠，合并
merged[-1][1] = max(merged[-1][1], interval[1])
else:
# 不重叠，直接加入
merged.append(interval)
return merged
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)（存储结果）
划分字母区间（LC 763）
题意：将字符串划分为尽可能多的片段，使得每个字母最多出现在一个片段中。
贪心思路：先记录每个字母最后出现的位置。然后从左到右扫描，维护当前片段的右边界（当前片段内所有字母的最远出现位置）。当扫描到右边界时，就完成一个片段的划分。
def partitionLabels(s: str) -> list[int]:
# 记录每个字符最后出现的位置
last = {ch: i for i, ch in enumerate(s)}
result = []
start = 0 # 当前片段起点
end = 0 # 当前片段的右边界
for i, ch in enumerate(s):
end = max(end, last[ch]) # 扩展右边界
if i == end:
# 到达边界，切一刀
result.append(end - start + 1)
start = i + 1
return result
- 时间复杂度：O(n)
- 空间复杂度：O(1)（字母表大小固定为 26）
经典题目列表
按难度分组，建议按顺序刷：
入门
| 题号 | 题目 | 核心思路 |
|---|---|---|
| 455 | 分发饼干 | 排序 + 双指针贪心 |
| 860 | 柠檬水找零 | 模拟 + 贪心找零 |
| 1005 | K 次取反后最大化的数组和 | 排序 + 贪心翻转最小值 |
进阶
| 题号 | 题目 | 核心思路 |
|---|---|---|
| 55 | 跳跃游戏 | 维护最远可达位置 |
| 45 | 跳跃游戏 II | 层级 BFS 思想 |
| 122 | 买卖股票的最佳时机 II | 累加所有正差价 |
| 56 | 合并区间 | 排序 + 贪心合并 |
| 763 | 划分字母区间 | 记录最远位置 + 滑动边界 |
挑战
| 题号 | 题目 | 核心思路 |
|---|---|---|
| 134 | 加油站 | 累计亏损 + 起点重置 |
| 435 | 无重叠区间 | 按右端点排序，经典区间调度 |
学习建议
- 先学思想：理解算法核心思路比背代码重要。
- 多画图：画出贪心每一步的选择过程，帮助理解为什么局部最优能推出全局最优。
- 归纳模板：每类贪心题（区间类、跳跃类、分配类）总结自己的解题模板。
- 重复练习：同类题目做 5 道以上形成肌肉记忆。
- 对比 DP：遇到贪心不确定的题，先试贪心再想 DP，体会两者的区别。
小结
- 贪心的难点不在编码，而在证明正确性。面试中能简要说清楚”为什么这样选是对的”就够了。
- 面试中常见的贪心题型：
- 区间调度：合并区间、无重叠区间、会议室问题
- 跳跃类：跳跃游戏系列
- 分配类：分发饼干、任务分配
- 记住一个口诀：排序是贪心的好朋友，大部分贪心题第一步都是排序。