贪心算法的代码往往不长，难点在于为什么当前选择不会影响全局最优。面试里如果只写代码，不解释贪心策略，很容易被追问到卡住。
可以先记一个判断方式：如果问题可以通过排序或维护一个当前最优边界，每一步做出局部选择，并且这个选择不会破坏后续最优解，就可以尝试贪心。
面试考察重点
- 能找出贪心策略。
- 能用交换、反证或直觉边界说明策略合理。
- 能处理排序后的遍历条件。
- 能区分贪心和动态规划。
贪心题怎么想？
贪心题最怕“凭感觉选”。写代码前至少要说清两个东西：
- 每一步贪的是什么，比如结束时间最早、当前能跳到最远、当前收益为正。
- 为什么这个选择不会让后面变差。
证明不一定要很形式化，但要能讲出取舍。比如区间调度里，选择结束最早的区间，是因为它给后面留下的可选空间最大；如果选择一个结束更晚的区间，不会让答案变得更多。
常见题型
| 题型 | 贪心策略 | 代表题 |
| --- | --- | --- |
| 分配问题 | 优先满足最容易满足的对象 | 分发饼干 |
| 股票买卖 | 把所有正收益累加 | 买卖股票的最佳时机 II |
| 跳跃问题 | 维护当前能到达的最远位置 | 跳跃游戏 |
| 区间问题 | 按右端点或左端点排序 | 无重叠区间、用最少数量的箭引爆气球 |
| 字符串重构 | 维护剩余可用次数或最远覆盖位置 | 划分字母区间 |
贪心常常和排序一起出现，因为排序能让“当前最优选择”变得明确。区间题经常按左端点或右端点排序，分配题经常把需求和资源都排序后用双指针匹配。
跳跃游戏模板
boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) {
return false;
}
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}farthest 表示当前能到达的最远位置。遍历到 i 时，如果 i > farthest，说明当前位置根本不可达。
这题的贪心点是：不关心具体从哪一步跳到 i，只关心当前能覆盖到的最远位置。只要当前位置在覆盖范围内，就可以用它继续更新覆盖范围。
“跳跃游戏 II”多了一个最少步数。它维护两个边界：
curEnd：当前步数能覆盖到的最远位置。farthest：在当前覆盖范围内再跳一步能到的最远位置。
当遍历到 curEnd 时，说明当前步数的范围用完了，必须多跳一步，并把 curEnd 更新为 farthest。
区间贪心模板
以无重叠区间为例，按右端点升序排序，每次保留结束最早的区间：
int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int count = 1;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
count++;
end = intervals[i][1];
}
}
return intervals.length - count;
}结束越早，留给后面区间的空间越大，这是这类题的核心选择。
区间题最容易错在排序字段。几个常见选择：
- 要选最多不重叠区间：按右端点升序。
- 要合并区间：按左端点升序。
- 要用最少箭引爆气球：按右端点升序，尽量用当前箭覆盖更多气球。
如果一个贪心策略不好解释，先用小样例找反例。比如“每次选长度最短的区间”看起来合理，但并不能保证选出最多不重叠区间。
贪心和动态规划怎么区分？
| 对比点 | 贪心 | 动态规划 |
| --- | --- | --- |
| 决策方式 | 当前一步直接选 | 依赖前面多个状态 |
| 是否回看历史 | 通常不回看 | 需要状态转移 |
| 证明重点 | 当前选择不会破坏全局最优 | 最优子结构和重叠子问题 |
| 常见题 | 区间、跳跃、分配 | 背包、子序列、路径 |
如果当前选择看起来合理，但举个小反例就会错，那它更可能需要 DP 或搜索。
易错点
- 贪心题常常需要先排序，排序字段错了答案就错。
- 区间题要看边界是否允许相等，比如
[1,2]和[2,3]是否重叠。 - 跳跃游戏 II 里“步数增加”的时机和当前覆盖边界有关。
- 贪心策略要能解释，不要只说“每次选最优”。
高频问题自测
- 贪心和动态规划怎么区分？
- 区间题为什么经常按右端点排序？
- 跳跃游戏里为什么只维护最远可达位置就够了？
- 贪心题怎样用交换或反证说明策略正确？
- 区间边界允许相等时，判断条件应该怎么写？
推荐练习题
写在最后
如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。
JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。
如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。