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

Guide约 1429 字大约 5 分钟

贪心算法的代码往往不长，难点在于为什么当前选择不会影响全局最优。面试里如果只写代码，不解释贪心策略，很容易被追问到卡住。

可以先记一个判断方式：如果问题可以通过排序或维护一个当前最优边界，每一步做出局部选择，并且这个选择不会破坏后续最优解，就可以尝试贪心。

面试考察重点

能找出贪心策略。
能用交换、反证或直觉边界说明策略合理。
能处理排序后的遍历条件。
能区分贪心和动态规划。

贪心题怎么想？

贪心题最怕“凭感觉选”。写代码前至少要说清两个东西：

每一步贪的是什么，比如结束时间最早、当前能跳到最远、当前收益为正。
为什么这个选择不会让后面变差。

证明不一定要很形式化，但要能讲出取舍。比如区间调度里，选择结束最早的区间，是因为它给后面留下的可选空间最大；如果选择一个结束更晚的区间，不会让答案变得更多。

常见题型

题型	贪心策略	代表题
分配问题	优先满足最容易满足的对象	分发饼干
股票买卖	把所有正收益累加	买卖股票的最佳时机 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 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。