专题 11贪心算法

11.1什么时候能贪，什么时候必须 DP

贪心算法的本质假设是：局部最优选择，累积起来就是全局最优。这个假设成立，贪心才正确；不成立，就得用 DP 枚举所有选择。

一个「贪心会错」的反例（必看）

拿 10.5 零钱兑换 改一下：硬币面额是 {1, 3, 4}，要凑出金额 6，求最少硬币数。

如果「贪心」——每次都选不超过剩余金额的最大面额：6 先选 4，剩 2 再选 1、1。于是 4+1+1 = 6，用了 3 个硬币。

但最优解是 3+3 = 6，只用 2 个硬币！贪心给出的 3 个并不是最少。

贪心：6 -> 选4 -> 剩2 -> 选1 -> 选1   共 3 枚  (4+1+1)
最优：6 -> 选3 -> 选3                共 2 枚  (3+3)

为什么贪心错了？因为「先塞一个大面额」这个局部最优，可能让剩下的零头变得不好凑（剩 2 只能用 1+1）。 局部最优没有推出全局最优。这题的正确解法是 DP（完全背包），把所有组合都考虑一遍才安全。

那贪心什么时候一定对

有两类情况贪心「通常」安全（但最好仍有证明或反例验证）：

• 区间调度类：每次选「结束最早」的区间，能腾出最多时间给后面——这类有严格证明，贪心必胜。
• 「维护极值后推导」类：如买卖股票维护历史最低价、跳跃游戏维护能到的最远位置，这些「状态只增不减」的题，当前最优能自然传导。

一句话总结本章立场：贪心不是「更优的 DP」，而是「在能证明成立的前提下，比 DP 更简单的写法」。 证明不了，就老老实实 DP。

贪心 vs DP：什么时候该用哪个（决策表）

拿到题如果犹豫「贪心还是 DP」，对照下面这张表快速定位：

记不住没关系，反例验证法永远是第一位的：先假设能贪，逼自己找个反例；找不到再写贪心，找到就换 DP。这张表只是帮你在「找反例之前」有个预判方向。

面试时怎么「证明」你的贪心

面试官常会追问「你这个贪心为什么是对的」。三种层级的回答，由弱到强：

• 反例验证（合格）：「我试过几个例子，包括故意构造的边界，没找到贪心失败的反例。」
• 交换论证（更好）：「假设存在一个最优解和我的贪心解在某步选择不同，把那个选择换成我的贪心选择，不会让结果变差。」区间调度就是用这个证明的——换掉一个晚结束的区间为早结束的，剩余可选空间只多不少。
• 数学归纳 / 最优子结构（最强）：「前 k 步贪心得到的是前 k 步的最优，第 k+1 步在剩余子问题上仍是同样结构。」买卖股票、跳跃游戏都属于这种。

日常刷题能说到「反例验证 + 交换论证」基本就稳了；真在面试里被深究，至少有话可说，而不是一句「直觉上是对的」。

11.2买卖股票的最佳时机（简单，力扣 121）

简单 核心：维护历史最低价

题意：给定每天的价格数组 prices，你只能买卖一次（先买后卖），求最大利润。 例如 prices = [7,1,5,3,6,4]，在第 2 天（价 1）买、第 5 天（价 6）卖，利润 5，是最大。

思路推导

暴力是枚举所有「买日 i < 卖日 j」的 pairs[i] - prices[i]，O(n²)。能不能一次遍历搞定？

关键转换：利润 = 卖出价 − 买入价。对你经过的每一个「卖日 j」，想让利润最大，就要让「买入价」尽可能低—— 而最低的买入价，就在 j 之前出现过。所以我们一边走一边记录「到今天为止的历史最低价」minPrice， 对每一天 j 算 prices[j] - minPrice，维护最大差值即可。

为什么这样对？因为 minPrice 是「截至 j 的最低」，prices[j] - minPrice 就是「在 j 及之前某天买、j 卖」的最大利润。 遍历所有 j 取最大，就覆盖了所有合法 (买,卖) 组合。这一步没有漏掉任何组合，又没重复算——这就是贪心成立的根基：历史最低价永远是可买的最优点。

参考代码

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;   // 历史最低买入价，初始化为极大值
        int maxProfit = 0;                   // 最大利润，最少为 0（不交易）
        for (int p : prices) {
            if (p < minPrice) {
                minPrice = p;                // 遇到更低价，更新最低买入价
            } else {
                // 否则尝试在今天卖出，看利润是否更大
                maxProfit = Math.max(maxProfit, p - minPrice);
            }
        }
        return maxProfit;
    }
}

也可以写成更直白的等价形式（每天先更新 minPrice，再算利润）：

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int p : prices) {
            minPrice = Math.min(minPrice, p);          // 维护历史最低
            maxProfit = Math.max(maxProfit, p - minPrice);
        }
        return maxProfit;
    }
}

复杂度：时间 O(n)（一遍扫描），空间 O(1)。n ≤ 10⁵，稳。

亲手走一遍：prices = [7,1,5,3,6,4]

day0 p=7: minPrice=7,  profit=max(0,7-7)=0
day1 p=1: 1<7 -> minPrice=1,  profit=0
day2 p=5: profit=max(0,5-1)=4
day3 p=3: profit=max(4,3-1)=4
day4 p=6: profit=max(4,6-1)=5   <- 最大利润出现在第5天卖
day5 p=4: profit=max(5,4-1)=5
最终 maxProfit = 5（第2天买价1，第5天卖价6）。

注意 minPrice 只在「遇到更低价」时更新，所以它始终代表「截至今天的历史最低买入点」； profit 则在对每夭的「今天卖」做候选比较。两者配合，等价于把 O(n²) 的所有 (买,卖) 对压缩成了一次扫描。

11.3跳跃游戏（中等，力扣 55）

中等 核心：维护「能到达的最远位置」

题意：数组 nums[i] 表示你在位置 i 最多能向右跳 nums[i] 步。问能否从下标 0 跳到最后一个下标。 例如 nums = [2,3,1,1,4] 可以（0→1→4）；nums = [3,2,1,0,4] 不行（到 3 后跳 0 步，卡住）。

思路推导

不要去真的「跳」——真正要回答的只是「最后一个位置在不在可达范围内」。 我们维护一个变量 reach = 当前能到达的最远下标。从左到右扫描：

• 每到一个位置 i，先检查 i > reach：如果连位置 i 都到不了，那更远的也别想了，直接 false。
• 否则，从 i 出发能最远到 i + nums[i]，用它与 reach 取较大者更新 reach。
• 只要 reach 覆盖到最后一个下标，就 true。

为什么这比 DP 简洁而且正确？DP 会算「每个位置能不能到」，但我们发现：只要「最远可达」一路追上最后下标，中间就一定有路—— 因为能到 reach 范围内的任意位置（每步至少走 1，可达性是连续的）。所以只需追一个 reach 就够了，不用存整个布尔数组。

参考代码

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;                       // 当前能到达的最远下标
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false;     // 连 i 都到不了，后面更到不了
            // 从 i 出发能到 i + nums[i]，更新最远可达
            reach = Math.max(reach, i + nums[i]);
            // 若已覆盖最后一个下标，提前成功
            if (reach >= nums.length - 1) return true;
        }
        return true;
    }
}

复杂度：时间 O(n)，空间 O(1)。n ≤ 10⁴，轻松。

亲手走一遍：nums = [2,3,1,1,4] 和 [3,2,1,0,4]

能到达的例子：

i=0: i<=reach(0) ok, reach=max(0,0+2)=2
i=1: i<=reach(2) ok, reach=max(2,1+3)=4  -> 已>=4(末位)，return true
剩余不用看，已经覆盖终点。

不能到达的例子 nums=[3,2,1,0,4]：

i=0: reach=max(0,0+3)=3
i=1: 1<=3 ok, reach=max(3,1+2)=3
i=2: 2<=3 ok, reach=max(3,2+1)=3
i=3: 3<=3 ok, reach=max(3,3+0)=3   <- 到位置3后最多还是到3，卡住
i=4: 4>reach(3) -> 连位置4都到不了，return false

关键就在 i=3 那一步：nums[3]=0 意味着从位置 3 一步都走不了，而 reach 停在 3，后面的 i=4 自然 i > reach 直接失败。 这个变量 reach 把「能不能到终点」整个压成了一行扫描，非常典型地体现了贪心「只追一个极值」的简洁。

11.4跳跃游戏 II（中等，力考 45）

中等 核心：「当前层边界」式贪心，步数最少

题意：同跳跃游戏，但保证一定能到达终点，求最少跳跃次数。 例如 nums = [2,3,1,1,4]，最少跳 2 次（0→1→4）。

思路推导

既然要「次数最少」，就不能走到哪算哪，得一层一层地跳。想象 BFS：第 1 跳能覆盖一个范围，第 2 跳在它基础上再往外扩。 我们用两个边界：

• curEnd：当前这一跳能覆盖的最远下标（也就是「这一层的终点」）。
• curFarthest：扫描当前层内所有位置时，能继续跳到的最远下标（下一层的终点）。

当我们走到 curEnd 时，说明「当前这层已经走完」，必须再跳一步才能继续往前——于是步数 +1， 并把下一层的边界更新为 curFarthest。这样每一层只跳一步，且每步都尽量远，自然步数最少（这是贪心：每层都选能到的最远，避免提前浪费跳跃）。

参考代码

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;                // 已经在终点，0 跳
        int jumps = 0;                       // 已跳次数
        int curEnd = 0;                      // 当前层的边界（这一跳能到的最远）
        int curFarthest = 0;                 // 扫描当前层能到达的下一层最远
        for (int i = 0; i < n - 1; i++) {    // 注意只需到 n-1，到达即停
            curFarthest = Math.max(curFarthest, i + nums[i]);
            if (i == curEnd) {               // 走到当前层边界，必须再跳一步
                jumps++;
                curEnd = curFarthest;        // 下一层的边界 = 本次能到的最远
                if (curEnd >= n - 1) break;  // 已覆盖终点，提前结束
            }
        }
        return jumps;
    }
}

复杂度：时间 O(n)，空间 O(1)。每个位置只扫一次。

亲手走一遍：nums = [2,3,1,1,4]

i=0: curFarthest=max(0,0+2)=2;  i==curEnd(0) -> jumps=1, curEnd=2
i=1: curFarthest=max(2,1+3)=4;  i(1)!=curEnd(2)
i=2: curFarthest=max(4,2+1)=4;  i(2)==curEnd(2) -> jumps=2, curEnd=4
i=3: curFarthest=max(4,3+1)=4;  i(3)!=curEnd(4)
i=4: 循环到 n-1=4 结束（其实到 i=3 后 curEnd=4 已 >= n-1，break）
结果 jumps = 2。

可以看到：第 1 跳（jumps=1）把边界推到 2，覆盖下标 0~2；第 2 跳（jumps=2）把边界推到 4，正好到终点。 两层对应两条跳跃路径，层数 = 最少步数，和 BFS 层序完全吻合。

11.5无重叠区间（中等，力扣 435）

中等 核心：按结束时间排序的区间调度

题意：给若干闭区间 intervals，删掉最少数量的区间，使剩下的互不重叠。返回要删的个数。 例如 intervals = [[1,2],[2,3],[3,4],[1,3]]，删掉 [1,3] 即可，返回 1。

思路推导

「删最少」等价于「留下最多且不重叠的区间」。这就是经典区间调度问题。 贪心策略（有严格证明）：每次选「结束最早」的区间。为什么？

结束得越早，后面留给其他区间的空间就越大。选了一个早结束的，就排除了所有与它重叠的（这些晚结束的本来也占更多空间）， 于是剩下的可选区间更多——局部最优（早结束）确实推出全局最优（留得最多）。

做法：

• 按每个区间的右端点升序排序。
• 依次遍历，维护上一个被选中的区间的结束时间 end。若当前区间左端点 ≥ end（不重叠），就保留它并更新 end；否则它重叠，计入「要删」。

参考代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 按区间右端点升序排序：贪心选「结束最早」的
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 0;                  // 被删（重叠）的区间个数
        int end = intervals[0][1];      // 上一个保留区间的结束时间
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                // 当前区间左端点 < 上一个个结束 -> 重叠，删掉当前
                count++;
            } else {
                // 不重叠，保留，并更新结束时间
                end = intervals[i][1];
            }
        }
        return count;
    }
}

复杂度：时间 O(n log n)（排序主导），空间 O(1)（忽略排序栈）。n ≤ 10⁵。

亲手走一遍：intervals = [[1,2],[2,3],[3,4],[1,3]]

先按右端点排序，得到 [[1,2],[2,3],[1,3],[3,4]]（右端点 2,3,3,4）。注意 [1,3] 和 [2,3] 右端点都是 3，顺序无关紧要：

保留 [1,2]，end=2
下一个 [2,3]：left=2 >= end=2 -> 不重叠，保留，end=3
下一个 [1,3]：left=1 < end=3  -> 重叠，删掉（count=1）
下一个 [3,4]：left=3 >= end=3 -> 不重叠，保留，end=4
最终 count = 1，删 [1,3] 即可。

为什么保留 [1,2] 而不是 [1,3]？因为 [1,2] 结束更早（2 < 3），给后面 [2,3]、[3,4] 腾出了位置； 若贪心选了 [1,3]，那 [2,3] 和 [3,4] 都会因重叠被删，留下的更少。「结束最早 → 留得最多」在这个例子里一目了然。

11.6区间题的通用套路

区间/线段类题在面试里出现频率很高，而且套路集中。下面这张表把「按什么排序、适合什么问题」一次性列清：

11.7本专题常见坑

11.8自测题