贪心 解题模板

适用场景

局部最优→全局最优的问题（区间调度、跳跃游戏、股票买卖）

常见模式

区间调度

 
# 最少移除 = 总数 - 最多不重叠
 
intervals.sort(key=lambda x: x[1])  # 按右端点排序
 
count, end = 1, intervals[0][1]
 
for s, e in intervals[1:]:
 
    if s >= end:
 
        count += 1
 
        end = e
 

区间覆盖 / 跳跃

 
# 能否跳到终点
 
max_reach = 0
 
for i in range(n):
 
    if i > max_reach: return False
 
    max_reach = max(max_reach, i + nums[i])
 
# 最少跳跃次数
 
jumps = cur_end = max_pos = 0
 
for i in range(n-1):
 
    max_pos = max(max_pos, i + nums[i])
 
    if i == cur_end:
 
        jumps += 1
 
        cur_end = max_pos
 

股票买卖

 
# 单次交易：维护最低价
 
min_price = float('inf')
 
max_profit = 0
 
for p in prices:
 
    min_price = min(min_price, p)
 
    max_profit = max(max_profit, p - min_price)
 
# 多次交易：累加所有上涨
 
profit = 0
 
for i in range(1, len(prices)):
 
    if prices[i] > prices[i-1]:
 
        profit += prices[i] - prices[i-1]
 

复杂度总结

模式	时间	空间	典型题
区间调度	O(n log n)	O(1)	无重叠区间、气球引爆
跳跃游戏	O(n)	O(1)	55、45
股票买卖	O(n)	O(1)	121、122
任务调度	O(n)	O(1)	621

关键要点

• 贪心需要证明！常用交换论证法

• 按右端点排序的区间调度是标准贪心

• 跳跃游戏 II = BFS 的贪心实现

→ 查看该分类题目：LeetCode学习路线图 > 十一、贪心

---

关联题型

关联题型	常见结合方式	典型题目
动态规划	贪心是DP的特例	122买卖股票II, 55跳跃游戏
排序	排序 + 贪心选择	452箭气球, 435无重叠
堆	堆维护贪心策略	621任务调度器