greedy.md

title	贪心算法面试题总结：区间贪心、跳跃游戏与证明思路
description	贪心算法面试题总结，讲解贪心题型识别、排序贪心、区间贪心、跳跃游戏、贪心证明思路和 LeetCode 高频题。
category	计算机基础
tag	算法
head	meta name content keywords 贪心算法,贪心算法模板,区间贪心,排序贪心,跳跃游戏,贪心证明,LeetCode贪心,算法面试题

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

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

面试考察重点

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

贪心题怎么想？

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

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

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

常见题型

题型	贪心策略	代表题
分配问题	优先满足最容易满足的对象	分发饼干
股票买卖	把所有正收益累加	买卖股票的最佳时机 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;
}

结束越早，留给后面区间的空间越大，这是这类题的核心选择。

区间题最容易错在排序字段。几个常见选择：

• 要选最多不重叠区间：按右端点升序。
• 要合并区间：按左端点升序。
• 要用最少箭引爆气球：按右端点升序，尽量用当前箭覆盖更多气球。

如果一个贪心策略不好解释，先用小样例找反例。比如“每次选长度最短的区间”看起来合理，但并不能保证选出最多不重叠区间。

代表题精讲：用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球 是区间贪心的典型题。题目给出一组气球区间 [start, end]，一支箭射在某个坐标 x 上，只要 start <= x <= end，这个气球就会被引爆，要求用最少的箭引爆所有气球。

这题的贪心点是：每次把箭射在当前可选区间的最右边界。先按右端点升序排序，第一支箭放在第一个气球的右端点。后面的气球如果左端点 <= arrow，说明这支箭还能覆盖它；如果左端点 > arrow，说明当前箭已经够不到了，必须新增一支箭，并把新箭放在这个气球的右端点。

代码里要注意两个边界：空数组返回 0；排序比较器不要写成 a[1] - b[1]，极端坐标下可能溢出。

int findMinArrowShots(int[][] points) {
    if (points.length == 0) {
        return 0;
    }
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1;
    int arrow = points[0][1];
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > arrow) {
            arrows++;
            arrow = points[i][1];
        }
    }
    return arrows;
}

如果样例是 [[10,16],[2,8],[1,6],[7,12]]，按右端点排序后是 [1,6]、[2,8]、[7,12]、[10,16]。第一支箭放在 6，能覆盖前两个区间；遇到 [7,12] 时左端点已经大于 6，必须新增一支箭，放在 12，它又能覆盖 [10,16]。最终答案是 2。

贪心和动态规划怎么区分？

对比点	贪心	动态规划
决策方式	当前一步直接选	依赖前面多个状态
是否回看历史	通常不回看	需要状态转移
证明重点	当前选择不会破坏全局最优	最优子结构和重叠子问题
常见题	区间、跳跃、分配	背包、子序列、路径

如果当前选择看起来合理，但举个小反例就会错，那它更可能需要 DP 或搜索。

易错点

• 贪心题常常需要先排序，排序字段错了答案就错。
• 区间题要看边界是否允许相等，比如 [1,2] 和 [2,3] 是否重叠。
• 跳跃游戏 II 里“步数增加”的时机和当前覆盖边界有关。
• 贪心策略要能解释，不要只说“每次选最优”。

高频问题自测

• 贪心和动态规划怎么区分？
• 区间题为什么经常按右端点排序？
• 跳跃游戏里为什么只维护最远可达位置就够了？
• 贪心题怎样用交换或反证说明策略正确？
• 区间边界允许相等时，判断条件应该怎么写？

推荐练习题

• 455. 分发饼干
• 122. 买卖股票的最佳时机 II
• 55. 跳跃游戏
• 45. 跳跃游戏 II
• 435. 无重叠区间
• 763. 划分字母区间