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

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

面试考察重点

面试考察重点

能找出贪心策略。

能用交换、反证或直觉边界说明策略合理。

能处理排序后的遍历条件。

能区分贪心和动态规划。

贪心题怎么想？

贪心题怎么想？

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

每一步贪的是什么，比如结束时间最早、当前能跳到最远、当前收益为正。

为什么这个选择不会让后面变差。

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

常见题型

常见题型

题型贪心策略代表题分配问题优先满足最容易满足的对象分发饼干股票买卖把所有正收益累加买卖股票的最佳时机 II跳跃问题维护当前能到达的最远位置跳跃游戏区间问题按右端点或左端点排序无重叠区间、用最少数量的箭引爆气球字符串重构维护剩余可用次数或最远覆盖位置划分字母区间

题型贪心策略代表题

题型

贪心策略

代表题

分配问题优先满足最容易满足的对象分发饼干

分配问题

优先满足最容易满足的对象

分发饼干

股票买卖把所有正收益累加买卖股票的最佳时机 II

股票买卖

把所有正收益累加

买卖股票的最佳时机 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;
}
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，说明当前位置根本不可达。

farthest
i
i > farthest

这题的贪心点是：不关心具体从哪一步跳到 i，只关心当前能覆盖到的最远位置。只要当前位置在覆盖范围内，就可以用它继续更新覆盖范围。

i

“跳跃游戏 II”多了一个最少步数。它维护两个边界：

curEnd：当前步数能覆盖到的最远位置。

curEnd

farthest：在当前覆盖范围内再跳一步能到的最远位置。

farthest

当遍历到 curEnd 时，说明当前步数的范围用完了，必须多跳一步，并把 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;
}
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;
}

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

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

要选最多不重叠区间：按右端点升序。

要合并区间：按左端点升序。

要用最少箭引爆气球：按右端点升序，尽量用当前箭覆盖更多气球。

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

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

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

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

452. 用最少数量的箭引爆气球

[start, end]
x
start <= x <= end

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

<= arrow
> arrow

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

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;
}
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。

[[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] 是否重叠。

[1,2]
[2,3]

跳跃游戏 II 里“步数增加”的时机和当前覆盖边界有关。

贪心策略要能解释，不要只说“每次选最优”。

高频问题自测

高频问题自测

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

区间题为什么经常按右端点排序？

跳跃游戏里为什么只维护最远可达位置就够了？

贪心题怎样用交换或反证说明策略正确？

区间边界允许相等时，判断条件应该怎么写？

推荐练习题

推荐练习题

  1. 分发饼干

455. 分发饼干

  1. 买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II

  1. 跳跃游戏

55. 跳跃游戏

  1. 跳跃游戏 II

45. 跳跃游戏 II

  1. 无重叠区间

435. 无重叠区间

  1. 划分字母区间

763. 划分字母区间

写在最后

写在最后

如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。

GitHub

Gitee

JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。

如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。

知识星球