11 · 贪心算法
来源： 代码随想录贪心专题 + labuladong 贪心框架
核心价值： 每一步选局部最优，期望达到全局最优
题量： 4 题
一、本质理解
labuladong 将贪心定位为”穷举 + 剪枝”的一种特殊形式——在每一步都选择当前看起来最优的方案。
贪心 vs DP
| 对比 | 贪心算法 | 动态规划 |
|---|---|---|
| 决策方式 | 只考虑局部最优 | 考虑所有可能 |
| 适用范围 | 满足贪心选择性质 | 更通用 |
| 效率 | O(n) 或 O(n log n) | 通常 O(n²) |
| 难度 | 难在证明”贪心是对的” | 难在找状态转移 |
代码随想录的”反例验证法”
“如果想不到反例，那贪心策略就是对的。“
二、核心模板
买卖股票的最佳时机（维护最低价）
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
# 更新历史最低价
if price < min_price:
min_price = price
# 更新最大利润
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit跳跃游戏（维护最远可达位置）
def can_jump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach: # 无法到达当前位置
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return True划分字母区间（区间贪心）
def partition_labels(s):
# 记录每个字符最后出现的位置
last_pos = {}
for i, ch in enumerate(s):
last_pos[ch] = i
res = []
start = end = 0
for i, ch in enumerate(s):
end = max(end, last_pos[ch])
if i == end: # 到达当前段边界
res.append(end - start + 1)
start = i + 1
return res三、Hot 100 贪心题目清单
| 题号 | 题目 | 难度 | 核心思路 | 建议用时 |
|---|---|---|---|---|
| 121 | 买卖股票最佳时机 | Easy | 维护最低价 | 20 min |
| 55 | 跳跃游戏 | Medium | 维护最远可达 | 25 min |
| 45 | 跳跃游戏 II | Medium | 维护边界+最少步数 | 30 min |
| 763 | 划分字母区间 | Medium | 记录末位置+区间贪心 | 30 min |
四、易错点与技巧
- 贪心的核心是策略：先大胆假设贪心策略，再努力找反例
- 排序预处理：很多贪心题需要先排序（区间类、分配类）
- 局部最优 ≠ 全局最优：贪心不是万能的，遇到反例就换 DP
- 边界维护：跳跃游戏的 max_reach 和区间问题的 end 都是典型技巧
五、复杂度总结
| 题目 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 买卖股票 | O(n) | O(1) |
| 跳跃游戏 | O(n) | O(1) |
| 划分字母区间 | O(n) | O(1)，字符集大小固定 |
六、参考与延伸
- 10-动态规划（DP 是贪心的通用版）
- labuladong 贪心：https://labuladong.online/algo/
- 代码随想录贪心专题：https://programmercarl.com/