贪心
本章目标：理解贪心选择性质，掌握跳跃游戏、区间调度等经典贪心模型。
你将学到
- 贪心选择性质的含义
- 跳跃游戏模型
- 区间调度与区间合并
- 分发糖果模型
- 什么时候贪心不成立
- 贪心与 DP 的区别
1. 概念
贪心算法在每一步选择中都采取当前状态下最优的选择，期望最终得到全局最优解。贪心成立的条件是贪心选择性质：局部最优能推导出全局最优。
贪心 vs 动态规划：
- DP：穷举所有状态，保证最优，但通常 O(n²) 以上
- 贪心：只选当前最优，O(n log n) 或 O(n)，但不保证正确
验证贪心策略是否正确的常用方法：反证法——假设存在更优解与贪心选择矛盾，推出矛盾。
2. 核心模板
区间调度（选最多不重叠区间）
python
def eraseOverlapIntervals(intervals):
"""移除最少区间使剩余不重叠 = 选最多不重叠区间"""
if not intervals:
return 0
intervals.sort(key=lambda x: x[1]) # 按右端点排序
count = 1
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] >= end: # 不重叠
count += 1
end = intervals[i][1]
return len(intervals) - count跳跃游戏（贪心）
python
def canJump(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复杂度
- 区间调度：排序 O(n log n) + 遍历 O(n)
- 跳跃游戏：O(n)
3. 经典题目精讲
LeetCode 45 · 跳跃游戏 II
题意：给定非负整数数组，每个元素代表最大跳跃步数，求到达末尾的最少跳跃次数。
思路：贪心——在当前跳跃范围内选下一步能到达最远的位置。
python
def jump(nums):
if len(nums) <= 1:
return 0
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
if cur_end >= len(nums) - 1:
break
return jumpsLeetCode 135 · 分发糖果
题意：N 个孩子站成一排，每个孩子有评分。给每个孩子发糖果，要求：评分高的孩子比相邻的孩子糖果多。求最少糖果数。
思路：两次遍历——从左到右保证右边评分高的比左边多，从右到左保证左边评分高的比右边多。
python
def candy(ratings):
n = len(ratings)
candies = [1] * n
# 从左到右
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# 从右到左
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)LeetCode 452 · 用最少数量的箭引爆气球
题意：给定气球区间，一支箭可以引爆一列上所有重叠的气球，求最少箭数。
思路：按右端点排序，贪心地在最右端射箭。
python
def findMinArrowShots(points):
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]
for s, e in points[1:]:
if s > end: # 当前气球不被上一支箭覆盖
arrows += 1
end = e
return arrows4. 易错点
- ⚠️ 贪心策略不一定是正确的——如 0-1 背包问题贪心（按性价比）不成立
- ⚠️ 区间问题注意排序依据：求最多不重叠按右端点，合并区间按左端点
- ⚠️ 分发糖果必须两次遍历，单次会遗漏一个方向的约束
5. 推荐刷题清单
| 题号 | 题名 | 难度 | 关键 |
|---|---|---|---|
| 55 | 跳跃游戏 | Medium | 贪心可达性 |
| 45 | 跳跃游戏 II | Medium | 贪心最少步数 |
| 135 | 分发糖果 | Hard | 双向贪心 |
| 435 | 无重叠区间 | Medium | 区间调度 |
| 452 | 用最少箭引爆气球 | Medium | 区间贪心 |
| 621 | 任务调度器 | Medium | 贪心+模拟 |
延伸阅读
- LeetCode 官方
- 代码随想录
- 《算法导论》(CLRS) 第 16 章