贪心算法每一步都拿走当前看来最好的选择，并且永不回头。它成立的前提极其苛刻——局部最优必须能无损地拼出全局最优，所以贪心的核心功夫不在写代码，而在证明「这一步选下去不会后悔」。

它解决什么问题

一类最优化问题中，全局解可以拆成一连串决策，且每步决策只依赖当前局面、不依赖未来。如果此时存在某种「局部最优选择」——选完它之后，剩余子问题的最优解拼起来仍是全局最优——那就不必像动态规划那样维护整张状态表，只需一个变量沿着最优路径走下去，复杂度常常从多项式再降一档。代价是适用范围窄：绝大多数问题里局部最优与全局最优并不一致，贪心只是少数幸运问题的特权解法。

核心原理

贪心选择性质与最优子结构

贪心成立需要两个性质：

  1. 贪心选择性质：全局最优解可以通过一系列局部最优选择得到，即每一步的当前最优都是「安全」的——存在某个全局最优解包含这个选择。
  2. 最优子结构：做出选择后，剩余子问题的最优解能与该选择拼成原问题的最优解。这一条与动态规划共享。

区别在于：DP 在每个子问题上保留多个候选、最后汇总；贪心直接押注一个候选并丢弃其余。所以贪心可以看作「只保留单一路径的 DP」，效率更高，但正确性必须单独论证。判断一道题能否贪心，本质是判断能否证明这个押注是安全的。

交换论证：证明贪心的直觉工具

交换论证是最常用的证明武器，套路分三步：

  1. 假设存在一个最优解 OPT，它的第一步选择与贪心选择不同。
  2. 把 OPT 中那个选择「换」成贪心选择，论证交换之后解不会变差。
  3. 于是存在一个包含贪心选择的最优解——归纳下去，贪心的每一步都安全。

以区间调度为例：贪心选结束最早的区间 A。任取一个最优解，若它第一个选的区间 B 结束更晚，把 B 换成 A：A 结束更早，与后续所有区间更不会冲突，方案可行且数量不减。因此「选结束最早者」不损失任何可能性。这套「换成我也不亏」的直觉，就是交换论证的全部。

深入机制

区间调度与无重叠区间

求最多能选多少个互不重叠的区间，策略是按右端点升序排序，依次保留与上一个已选区间不冲突者：

int maxNonOverlap(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    int count = 0;
    long end = Long.MIN_VALUE;
    for (int[] itv : intervals) {
        if (itv[0] >= end) {
            count++;
            end = itv[1];
        }
    }
    return count;
}

直觉是「尽早腾出场地」：结束越早，留给后面的时间越多。需要警惕的是错误替代方案——按「时长最短」或「开始最早」排序都能构造出反例，面试中主动给出反例比只背结论更有说服力。细节上比较器要写 Integer.compare(a[1], b[1])，a[1] - b[1] 在极端坐标下会整数溢出。

跳跃游戏：不追踪路径，只维护边界

数组中每个元素表示在该位置最多能跳的步数，问能否到达末尾。贪心不枚举任何一条具体路径，只维护一个量：当前所有可达位置能延伸到的最远下标。

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 的所有路径中，对「能否继续向右」这件事唯一重要的信息就是它们覆盖的最远边界，其余细节对决策毫无影响——把指数级的路径空间压缩成一个标量，这正是贪心优越于搜索的地方。续作跳跃游戏 II 问最少步数，则维护两个边界：当前步数能覆盖的 curEnd，以及在覆盖范围内再跳一步能到的 farthest；扫描指针碰到 curEnd 时步数加一并把 curEnd 推进到 farthest。

加油站：把「总账」与「局部断点」分开看

环形路线上 n 个加油站，gas[i] 与 cost[i] 已知，问从哪站出发能绕一整圈。两条贪心结论：

  1. 若 sum(gas) < sum(cost)，总油量不够，必定无解。
  2. 从某起点出发，若在站 j 处油箱首次变负，则起点到 j 之间任何一站做起点都不行——能从起点走到 j，说明途中各站累计净收益非负，从中间任何位置出发到达 j 时油量只会更少。于是候选起点直接跳到 j+1，不必逐个验证。
int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {      // 当前起点失败，且中间各站都不可能
            start = i + 1;
            tank = 0;
        }
    }
    return total < 0 ? -1 : start;
}

一次扫描 O(n)，而枚举起点再逐站模拟是 O(n²)。这题是「排除法贪心」的范本：不是证明谁一定行，而是一次性排除一大片一定不行的。

分发饼干：排序 + 双指针的匹配类贪心

孩子有胃口 g，饼干有尺寸 s，一块饼干最多满足一个孩子，求最多能满足多少孩子。策略：胃口和饼干分别排序，用当前最小的饼干去尝试满足胃口最小的孩子——满足不了就换下一块饼干，满足了双方各进一步。大饼干留给胃口大的孩子不算浪费，交换论证同样适用：若某个最优方案里这孩子拿了更大的饼干，换成刚好能满足他的最小饼干，释放出的资源只会让方案不变差。总复杂度由排序主导，O(n log n)，匹配本身是线性双指针。

工程实践

  • 先找反例，再写代码：策略想出后，花一分钟构造小样例试图推翻它。构造不出再考虑证明；构造得出就直接换 DP，别犹豫。
  • 排序是贪心的常客：区间按端点、匹配按大小、重构按频次——排序让「当前最优」变得可定义。排序字段选错，全盘皆错。
  • 边界语义对齐题目：区间题里 [1,2] 与 [2,3] 算不算重叠，决定判断写 >= 还是 >。
  • 复杂度通常是排序主导的 O(n log n)：输入已有序时可降到线性，这也是贪心相对 DP 的主要卖点。

对比与权衡

维度 贪心 动态规划 回溯
决策方式 每步锁定局部最优 保留子问题的全部候选 试错加撤销
正确性依据 贪心选择性质（需证明） 最优子结构（自然成立） 穷举保证
时间复杂度 多为 O(n log n) 状态数 × 转移代价 指数级
反悔能力 无 无此概念 有
失效信号 当前选择影响未来收益 子问题不重叠 需要全部方案

判断流程可以反过来用：能证明贪心选择性质就上贪心；证明不了但子问题重叠，退回 DP；连最优子结构都不满足、或要求输出全部解，只能回溯搜索。

面试视角

贪心和 DP 的分界线在哪里？ 两者都要求最优子结构，差别在贪心选择性质：贪心每步只保留一个分支并断言它属于某个最优解，DP 不敢做这个断言，所以保留所有候选最后汇总。能证明「押注安全」就用贪心，证明不了就用 DP。

怎么向面试官证明贪心策略正确？ 首选交换论证：任取最优解，把它的第一步换成贪心选择，说明交换后解不变差，归纳得证。其次是反证：假设贪心结果更差，推出矛盾。证明都不出时，「找不到反例」只能算启发式依据，面试中要明确承认这一点。

跳跃游戏为什么不需要记录具体路径？ 因为决策只依赖一个信息——可达范围的最远边界，所有路径在这件事上等价。维护 farthest 一个变量就压缩了全部路径信息，这是从搜索到贪心的关键一跃。

区间题为什么常按右端点排序？ 右端点决定「何时腾出资源」。按右端点升序、每次选结束最早者，能给剩余区间留下最大的可用空间，交换论证可证其安全；按左端点排序管的是「先来后到」，适合合并区间而非计数。

小结

  • 贪心 = 局部最优选择 + 永不回头，成立前提是贪心选择性质，必须论证。
  • 交换论证的口诀：把最优解的第一步换成我的选择，证明不亏，然后归纳。
  • 四大经典模型：区间调度按右端点、跳跃游戏维护最远边界、加油站一次性排除不可行起点、分发饼干排序双指针。
  • 证不出贪心性质就退到 DP，要枚举全部方案就退到回溯——三种范式是退化与兜底的关系，不是并列的口味偏好。