贪心算法面试题总结：区间贪心、跳跃游戏与证明思路

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