贪心算法：局部最优与证明思维

学“贪心算法：局部最优与证明思维”时，我走过的弯路可以概括成一句话：贪心题最让我不踏实的地方是代码通常很短，但我不知道这次选了局部最优，后面会不会把正确答案堵死。问题不在于知识点有多难，而在于我一开始只盯着结果，没有看到它在维护什么关系。下面是我重新补这块基础时留下的笔记。

贪心算法看起来最像“凭感觉做选择”，但真正可靠的贪心绝对不能只靠感觉。它的核心是：每一步选择局部最优，并且这个选择不会破坏全局最优。

所以学贪心，重点不是代码，而是证明。

贪心算法从候选、局部选择到证明的过程

它从哪里来

贪心不是一种特定代码模板。最小生成树、编码和调度问题的研究逐步形成了“每次做局部安全选择”的方法。它真正困难的部分一直是证明：为什么这个选择不会堵死全局最优，而不是写出排序加循环。

贪心适合什么问题

贪心通常适合具有这些特征的问题：

可以拆成一系列选择。
每一步有明确的局部最优策略。
局部最优选择可以导向全局最优。
做出选择后，不需要回头修改前面的选择。

典型问题：

区间调度。
合并区间。
跳跃游戏。
分发糖果。
Huffman 编码。
最少箭射气球。
买卖股票的部分变体。

区间调度

问题：给定若干会议区间，最多能安排多少个互不重叠的会议？

贪心策略：每次选择结束时间最早的会议。

int maxMeetings(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int count = 0;
    int end = Integer.MIN_VALUE;
    for (int[] in : intervals) {
        if (in[0] >= end) {
            count++;
            end = in[1];
        }
    }
    return count;
}

为什么不是选择开始最早、持续时间最短？因为结束越早，留给后续会议的空间越大。这个策略可以用交换论证证明：任意最优方案中第一个会议，都可以换成结束更早的会议，而不会让答案变差。

跳跃游戏

问题：数组每个位置表示最远能跳多远，判断能否到达最后。

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，就能继续扩展可达范围。

分发糖果

问题：每个孩子有评分，相邻孩子评分高的糖果更多，求最少糖果数。

这题需要两次贪心：

从左到右，保证右边评分高于左边时糖更多。
从右到左，保证左边评分高于右边时糖更多。

int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }
    int sum = 0;
    for (int c : candies) sum += c;
    return sum;
}

这题很适合说明：贪心不一定只扫一遍，有时要分别满足多个局部约束。

贪心和动态规划的区别

动态规划会保留多个状态，比较多个选择；贪心只保留当前看起来最好的选择。

如果一个问题每一步的最优选择不会影响未来最优性，可以贪心。否则就需要 DP 或搜索。

比如背包问题：

0-1 背包不能简单按价值、重量或性价比贪心，因为局部选择可能导致全局不优。
分数背包可以贪心，因为物品可以拆分，按性价比拿一定最优。

贪心证明方法

常见证明思路：

交换论证：把最优解中的某个选择换成贪心选择，不会变差。
反证法：假设贪心选择不在最优解中，推出矛盾。
保持不变量：每一步后都保持某个最优性质。
归纳法：证明第一步正确，后续子问题同样成立。

写贪心题解时，至少要说清楚为什么这个局部策略不会挡住未来。

常见错误

样例能过就以为贪心正确。
没有证明局部最优能推出全局最优。
排序维度选错。
区间开闭边界处理错误。
把需要 DP 的问题硬贪心。
遇到多个约束时只满足其中一个。

工程场景

贪心在工程里常用于调度和资源分配：

缓存淘汰策略中的局部选择。
任务调度优先级。
区间合并和冲突检测。
带宽、机器、预算的近似分配。
编码压缩中的 Huffman 树。

工程中的贪心常常不是求严格最优，而是在复杂约束下求足够好、足够快的方案。此时要明确这是近似策略，而不是数学意义上的最优算法。

面试题

什么样的问题适合贪心？
贪心和动态规划有什么区别？
区间调度为什么选择结束时间最早？
为什么 0-1 背包不能简单按性价比贪心？
如何证明一个贪心策略正确？

小结

贪心最迷人的地方是简单，最危险的地方也是简单。真正可靠的贪心必须能证明。以后看到“每一步选当前最优”时，先不要急着写代码，先问：这个选择会不会让未来变差？