信息技术大学
贪心
数据结构与算法·面试高频 · 第 4 章 算法思想
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
贪心
数据结构与算法·面试高频 · 第 4 章 算法思想
贪心适用条件与证明思路
贪心不是玄学：局部最优能推全局最优才敢用，交换论证是最常用的证明。
选择性质
第一步的最优选择不关全局最优的门
交换论证
任一最优解都能换成贪心选择而不变差
反例意识
举不出反例不等于成立，存疑就退回 DP
区间调度四件套
不重叠、合并、插入、射气球：右端点排序一招鲜，区间题先排序再扫。
不重叠
按右端点贪心选，结束越早留给后面机会越多
合并区间
按左端点排序，重叠则延伸右端
插入区间
定位重叠带逐个合并，插到中间
射气球
右端点最小化，一箭穿所有重叠的
跳跃游戏
维护最远可达：扫一遍看当前位置是否够得着，够不着就卡死。
可达判定
最远边界落后于当前下标即失败
最少步数
层序思想：当前边界内选下一跳最远者
股票贪心
只许一次交易找最大差价，允许多次就把每段上涨都吃下：分解到天。
单次
记录历史最低价，每天尝试卖出一次
多次
所有正差值累加，等价于吃下每段上涨
含冷冻期
带约束转状态机 DP，贪心退场
本节要点
- ✓贪心敢用：交换论证或举反例
- ✓区间题：先排序再扫右端点
- ✓跳跃：维护最远可达边界
- ✓股票：单次记低点，多次吃涨幅
延伸主题：刷无重叠区间推一遍买卖股票 II
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1区间调度为什么按右端点排序是正确的？
参考答案交换论证：任一最优解的第一个区间都可换成右端点最早者——它结束更早，不会与后续任何选择冲突。归纳下去，贪心解的规模与最优解一致。
2跳跃游戏 II 求最少步数，为什么贪心层序是对的？
参考答案把「一步能到达的范围」当一层，层内扫描记录下一层的最远边界，走到边界步数加一。与 BFS 层序同构，层数就是步数，严格不漏。
3什么时候贪心会翻车，信号是什么？
参考答案局部最优互相冲突、当前选择影响后续可选结构时（背包、最长递增等）贪心常翻车。信号是「选择之间有后效性」，此时应列状态转移改用 DP。