贪心算法：证明方法与反例分析

贪心的核心思想

贪心（Greedy）：在每一步决策中，选取当前看起来最优的选择，期望局部最优能推导出全局最优。

关键验证：贪心策略并不总是正确的！必须证明贪心选择性（Greedy Choice Property） 和最优子结构（Optimal Substructure）。

贪心 vs 动态规划

如何证明贪心正确

方法一：交换论证（Exchange Argument）

假设最优解 OPT 中有一步选择 B，我们的贪心选了 A。
证明：把 OPT 中的 B 换成 A 后，值不会变差。
→ 所以可以把最优解"变换"成贪心解，贪心正确。

方法二：归纳法

归纳证明：在处理前 k 步后，贪心解和某个最优解同样"好"或更好。

方法三：直接反例法（否定错误贪心）

只需找一个反例，即可推翻错误的贪心策略。

区间调度——贪心经典

问题：给定 n 个区间，选出最多不重叠的区间数。

错误贪心：选开始最早的 → 反例：[1,10], [2,3], [4,5] 选了长区间丢失两个
错误贪心：选最短的     → 反例：[1,3], [2,4], [3,5] 短的 [2,4] 把两端都阻断

正确贪心：选结束时间最早的（为后续区间留最多空间）

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // 按结束时间排序
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= end) {  // 与上一个不重叠
            count++;
            end = interval[1];
        }
    }
    return count;
}

时间复杂度：O(n log n)（排序主导）

跳跃游戏——贪心维护"最远可达"

// LeetCode 55 - 是否能到达终点
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;         // i 不可达
        maxReach = Math.max(maxReach, i + nums[i]); // 贪心：维护最远距离
    }
    return true;
}

// LeetCode 45 - 最少跳跃次数
public int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {           // 到达当前跳跃边界，必须跳一步
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

分发糖果——双向贪心

// LeetCode 135：相邻孩子中评分更高的孩子必须获得更多糖果
public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candy = new int[n];
    Arrays.fill(candy, 1);
    // 从左到右：右边 > 左边，右边多一个
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 1;
    }
    // 从右到左：左边 > 右边，左边取 max
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) candy[i] = Math.max(candy[i], candy[i + 1] + 1);
    }
    int sum = 0;
    for (int c : candy) sum += c;
    return sum;
}

常见贪心模式归纳

常见反例与错误

问题：找零最少硬币数，硬币面值 [1, 3, 5]，凑 7 元
错误贪心：先选最大面值 5，剩 2 = 1+1 → 3 枚
正确答案：3+3+1 = 3 枚  ← 同样！这个例子贪心凑巧对了

凑 11 元：
错误贪心：5+5+1 = 3 枚
是否有更优？10+1? 币值没有10。5+3+3 = 3 枚，一样。

反例场景 [1, 5, 6]，凑 10：
贪心：6+1+1+1+1 = 5枚
最优：5+5 = 2枚  ← 贪心失败！

结论：零钱兑换不能总用贪心，需要 DP。

架构师速查表