贪心算法专题导读

贪心的直觉：局部最优 → 全局最优

贪心（Greedy）是一种做题时人人都"偷用过"的策略：每一步都做出当下看起来最优的选择，并且寄希望于这一连串局部最优最终拼出全局最优。

比如去食堂打饭，窗口一共 5 个，每个队都排着人。你的策略大概率是"挑最短的队排"——只看当前哪队最快，不去模拟 10 分钟后各队的变化。这就是贪心：决策只依赖当前局面，不回头、不反悔。

形式化一点，贪心算法有两个特征：

1. 无后效性地做选择：每一步从若干候选中选一个"局部最优"选项，选择一旦做出就不再更改；
2. 局部最优的叠加推出全局最优：这是贪心正确的前提，也是贪心题最大的不确定点——不是每道题都满足。

很多同学刷贪心的第一反应是"这题凭什么贪心是对的？"——问得好，这正是本专题要训练的核心：把"局部最优是什么"明说出来，再用例子或直觉论证它能推出全局最优。想不清楚这一步，代码写得再对也只是碰运气。

与 DP 的本质区别

贪心和 DP 经常被放在一起比较，因为两者都在做"逐步决策"。区别用一句话讲清：

举个直观例子：爬楼梯（70）要问"最少花多少体力到达顶"，每一步选择会互相影响，必须 DP 存状态；而"跳跃游戏能不能到终点"，只需要维护一个"当前最远可达位置"，一个变量就够——当每一步的最优选择不会让后续步骤变差时，就不需要 DP 那套记账。

一个实用判断：如果题目允许的每步选择之间有"此消彼长"的耦合（选 A 会导致 B 处变差），大概率要 DP；如果存在一个"当前拿走不亏"的顺序（如先满足最容易满足的），贪心往往可行。

什么问题"能"贪心：两个例子

例 1：分发饼干（455）

455. 分发饼干：每个孩子有胃口值 g[i]，每块饼干有尺寸 s[j]，饼干 j 能满足孩子 i 当且仅当 s[j] >= g[i]，一块饼干只能喂一个孩子，求最多满足多少孩子。

局部最优：用"尺寸最小的饼干"去喂"胃口最小的、能满足的孩子"，让大饼干留给胃口大的孩子。

论证：胃口小的孩子最容易满足。如果连最小的可用饼干都喂不了它，其他孩子更喂不了；先满足它绝不损害后续孩子——因为它吃掉的是"最不该浪费在大胃口孩子身上的小饼干"。这个"先易后难、资源按需匹配"的结构就是典型的可贪心场景。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0; // 指向下一个待满足的孩子
        // 饼干从小到大尝试；小饼干喂不动当前孩子，也不可能喂动后面的孩子
        for (int cookie = 0; cookie < s.length && child < g.length; cookie++) {
            if (s[cookie] >= g[child]) {
                child++; // 满足一个孩子
            }
        }
        return child;
    }
}

注意双指针的写法：饼干不合适时只移动饼干指针（小饼干谁也喂不饱，直接丢弃），合适时两个指针一起前进。这个"不合适就丢小的"的逻辑正是贪心决策。

例 2：跳跃游戏（55）

55. 跳跃游戏：数组每个元素表示该位置最大跳跃长度，判断能否到达最后一个下标。

局部最优：每走一步，都更新"从头开始最远能覆盖到哪里"（cover）。只要当前位置还在覆盖范围内，就不必关心具体从哪一步跳过来。

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;
        int cover = 0; // 当前可达的最远下标
        for (int i = 0; i <= cover; i++) {
            // 局部最优：贪心扩展可达范围
            cover = Math.max(cover, i + nums[i]);
            if (cover >= nums.length - 1) return true;
        }
        return false; // 覆盖范围停滞，够不到终点
    }
}

这里贪心成立的关键是：可达性只由"最远覆盖边界"决定，中间怎么跳不影响结论，所以一个变量就能代表全部状态。这个例子还展示了贪心题的一个技巧：把"选择"抽象成一个可维护的聚合量（覆盖范围、当前和、剩余次数），而不是纠结每一步的具体决策。

反例：贪心失效的场景

不是所有题都能贪心。经典反例是"凑硬币：面值 1、5、11，凑 15"：贪心每次拿最大的（11, 1, 1, 1, 1）需要 5 枚，而最优解 (5, 5, 5) 只要 3 枚。问题出在"拿最大面值"这个局部最优挤占了后续选择的灵活性——它不满足"每步最优不损害后续"的前提，所以必须用 DP。遇到拿不准的贪心题，构造一个反例输入快速验证是最快的止损方式。

贪心没有万能套路

必须坦率地讲：贪心是所有专题里"模板浓度"最低的。回溯有骨架、DP 有四步法，贪心只有一种通用的思考流程：

1. 拆解问题：把问题分解成一串按顺序做的决策；
2. 定义局部最优：明确说出每一步"选什么最划算"；
3. 推导全局最优：论证一连串局部最优为什么不会互相拆台；
4. 举反例验证：构造边界输入（极端值、重复值、临界恰好满足/不满足），看局部最优是否翻车。

想不出局部最优时，试试常见的贪心切入角度：排序后从最小/最大开始处理（饼干、无重叠区间）、维护一个聚合量（覆盖范围、累计利润）、两个维度分开处理（先保证一个维度有序再处理另一个，分发糖果、重建队列）。第 2 步和第 3 步是思维核心，第 4 步是纪律。

专题地图与题单

本专题按贪心技巧分五组推进，难度递增：

学习建议

• 每题先说策略再写码：动笔前用一句话说出"局部最优是什么"，说不出就说明还没想清楚；
• 横向对比同一组题：区间组四道题的排序键各不相同（左端点还是右端点），对比记忆效果最好；
• 接受不确定性：贪心没有严格模板，卡住时果断考虑反例或换 DP，不要在错误的贪心策略上死磕。

下一篇进入最成体系的区间调度一族：无重叠区间、合并区间、划分字母区间，一套"排序 + 比较"三板斧打天下。

参考

• 代码随想录 · 贪心算法专题