贪心算法
贪心算法（Greedy Algorithm）是一类在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的算法。它的核心思想非常直观：局部最优，步步为营。
贪心算法并不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。因此，贪心算法并不一定能得到整体最优解，但对很多特定问题，贪心策略确能产生全局最优解。
核心特征
贪心算法之所以简单，是因为它不需要回溯，一旦做出选择就不会改变。但这也意味着贪心算法有着严格的适用条件。
适用条件
一个问题能够用贪心算法求解，必须满足两个关键性质：
1. 贪心选择性质
问题的全局最优解可以通过一系列局部最优（贪心）选择来达到。这意味着当我们做出一个贪心选择后，原问题就变成了一个规模更小的子问题，而且这个子问题的最优解与之前的选择组合起来就是原问题的最优解。
例如在活动选择问题中，每次选择结束时间最早的活动，剩下的就是在剩余时间内安排最多活动。这个子问题与原问题形式相同，只是规模更小。
2. 最优子结构性质
问题的最优解包含其子问题的最优解。这个性质与动态规划相同，意味着我们可以通过组合子问题的最优解来构造原问题的最优解。
与动态规划的区别
贪心算法和动态规划都要求问题具有最优子结构，但两者的选择方式不同：
| 特性 | 贪心算法 | 动态规划 |
|---|---|---|
| 选择方式 | 自顶向下，做出选择后求解子问题 | 自底向上，先求子问题再做选择 |
| 子问题关系 | 每次选择后只有一个子问题 | 可能有多个重叠子问题 |
| 回溯 | 不回溯，选择后不再改变 | 会考虑所有可能的选择 |
| 效率 | 通常更高效 | 可能需要更多计算 |
举个例子，对于最短路径问题：
- Dijkstra算法（贪心）：每次选择距离起点最近的未访问节点，确定其最短路径后不再改变
- 动态规划：会考虑所有可能的路径，比较后选择最优
正确性证明方法
贪心算法的难点不在于实现，而在于证明其正确性。常用的证明方法有两种：
贪心保持领先（Greedy Stays Ahead）
核心思想：证明贪心算法在每一步的选择都"不比最优解差"，从而最终结果必然是最优的。
证明步骤：
- 定义一个度量标准，用于比较贪心解和最优解
- 证明在每一步，贪心解在这个度量上都不劣于最优解
- 推导出贪心解最终是最优解
以活动选择问题为例：有 n 个活动，每个活动有开始时间和结束时间，选择最多的互不冲突的活动。
贪心策略：按结束时间排序，每次选择结束最早且不冲突的活动。
证明思路：
- 设贪心解选择的活动序列为
- 设最优解为
- 用归纳法证明 的结束时间不晚于
- 由于每次贪心选择都是结束最早的，所以 结束不晚于
- 假设 成立，那么在选择第 个活动时，贪心解选择的是最早结束的可用活动，必然不晚于最优解的选择
- 因此 ，贪心解是最优的
交换论证（Exchange Argument）
核心思想：证明任何最优解都可以通过一系列交换操作变成贪心解，而不改变最优性。
证明步骤：
- 设 是任意一个最优解， 是贪心解
- 如果 ，找到第一个不同的地方
- 证明可以通过交换将 的这一部分变成 的对应部分，且不破坏最优性
- 重复这个过程直到 变成
以最小生成树的Kruskal算法为例：每次选择权重最小的边，如果不形成环就加入。
证明思路：
- 设贪心解的边集为 ，任一最优解为
- 如果 ，存在边 但
- 将 加入 会形成环，环上必存在边
- 由于贪心选择最小权重边，
- 用 替换 得到新的生成树，权重不增加
- 重复此过程，最终 变成 ，证明贪心解最优
经典问题详解
活动选择问题
有 n 个活动，每个活动有开始时间 和结束时间 ，选择最多的互不冲突的活动。
贪心策略：按结束时间排序，每次选择结束最早且与已选活动不冲突的活动。
为什么按结束时间排序？
直觉上，选择结束最早的活动，给后续活动留下最多的时间。按开始时间排序不能保证这一点：一个活动开始很早但持续很久，反而会阻碍后续很多活动。
public int activitySelection(int[][] activities) {
if (activities.length == 0) return 0;
// 按结束时间排序
Arrays.sort(activities, (a, b) -> a[1] - b[1]);
int count = 1; // 第一个活动必然选择
int lastEnd = activities[0][1];
for (int i = 1; i < activities.length; i++) {
// 如果当前活动的开始时间 >= 上一个选中活动的结束时间，则选择
if (activities[i][0] >= lastEnd) {
count++;
lastEnd = activities[i][1];
}
}
return count;
}
时间复杂度：（排序） 空间复杂度：
跳跃游戏（LeetCode 55）
给定一个非负整数数组，数组中每个元素代表你在该位置可以跳跃的最大长度，判断是否能到达最后一个位置。
贪心策略：维护当前能到达的最远位置，如果某个位置超过了最远位置，说明无法到达。
public boolean canJump(int[] nums) {
int maxReach = 0; // 当前能到达的最远位置
for (int i = 0; i < nums.length; i++) {
// 如果当前位置超过了能到达的最远位置，返回 false
if (i > maxReach) return false;
// 更新最远能到达的位置
maxReach = Math.max(maxReach, i + nums[i]);
// 如果已经能到达终点，提前返回
if (maxReach >= nums.length - 1) return true;
}
return true;
}
为什么贪心正确？
关键观察：如果在位置 能到达位置 （），那么位置 也能到达 到 之间的所有位置。所以只需要维护一个"能到达的最远位置"，不需要考虑具体的跳跃路径。
跳跃游戏 II（LeetCode 45）
在能到达终点的前提下，求最少的跳跃次数。
贪心策略：在当前跳跃范围内，选择能到达最远位置的点作为下一次跳跃的起点。
public int jump(int[] nums) {
if (nums.length <= 1) return 0;
int jumps = 0; // 跳跃次数
int currentEnd = 0; // 当前跳跃能到达的边界
int maxReach = 0; // 下一次跳跃能到达的最远位置
for (int i = 0; i < nums.length - 1; i++) {
// 更新下一次跳跃能到达的最远位置
maxReach = Math.max(maxReach, i + nums[i]);
// 到达当前跳跃边界，必须跳跃
if (i == currentEnd) {
jumps++;
currentEnd = maxReach;
// 如果已经能到达终点
if (currentEnd >= nums.length - 1) break;
}
}
return jumps;
}
这个算法模拟了一个"层次遍历"的过程：每次跳跃覆盖一个区间，在区间内找能到达的最远位置作为下一次跳跃的目标。
分发糖果（LeetCode 135）
有 n 个孩子站成一排，每个孩子有一个评分。需要给每个孩子分发糖果，满足：
- 每个孩子至少有一颗糖果
- 评分更高的孩子比相邻孩子得到更多糖果
求最少需要多少糖果。
贪心策略：两次遍历
- 从左到右：如果右边评分更高，糖果数 = 左边 + 1
- 从右到左：如果左边评分更高，糖果数 = max(当前值, 右边 + 1)
public 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;
}
}
// 从右到左：处理左孩子比右孩子评分高的情况
// 同时取 max，保证两个方向的约束都满足
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 total = 0;
for (int candy : candies) {
total += candy;
}
return total;
}
为什么需要两次遍历？
一次遍历无法同时处理左右两个方向的约束。比如数组 [1, 2, 3, 2, 1]：
- 从左到右只能保证递增部分正确
- 从右到左才能保证递减部分正确
- 取 max 保证两个约束同时满足
无重叠区间（LeetCode 435）
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
贪心策略：按结束时间排序，保留结束早的区间（与活动选择问题等价）。
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
// 按结束时间排序
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 1; // 保留的区间数
int lastEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
// 如果当前区间不与前一个保留的区间重叠，则保留
if (intervals[i][0] >= lastEnd) {
count++;
lastEnd = intervals[i][1];
}
// 否则移除当前区间（不更新 lastEnd）
}
return intervals.length - count;
}
用最少数量的箭引爆气球（LeetCode 452）
在二维空间中有球形气球，每个气球用水平直径的起点和终点表示。一支箭可以垂直射出，如果箭穿过气球的直径范围，气球就会引爆。求引爆所有气球最少需要多少支箭。
这个问题本质上与无重叠区间问题相同：找出最多不重叠的区间数量。
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
// 按结束位置排序
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1;
long lastEnd = points[0][1]; // 注意：用 long 避免溢出
for (int i = 1; i < points.length; i++) {
// 如果当前气球起点 > 上一箭位置，需要新箭
if (points[i][0] > lastEnd) {
arrows++;
lastEnd = points[i][1];
}
// 否则当前气球会被同一支箭引爆
}
return arrows;
}
划分字母区间（LeetCode 763）
字符串 S 由小写字母组成。将字符串划分为尽可能多的片段，使得同一字母最多出现在一个片段中。
贪心策略：
- 统计每个字母最后出现的位置
- 遍历字符串，维护当前片段的最远边界
- 当遍历到最远边界时，划分一个片段
public List<Integer> partitionLabels(String s) {
int[] lastIndex = new int[26]; // 每个字母最后出现的位置
// 统计每个字母最后出现的位置
for (int i = 0; i < s.length(); i++) {
lastIndex[s.charAt(i) - 'a'] = i;
}
List<Integer> result = new ArrayList<>();
int start = 0; // 当前片段的起点
int end = 0; // 当前片段的最远边界
for (int i = 0; i < s.length(); i++) {
// 更新当前片段的最远边界
end = Math.max(end, lastIndex[s.charAt(i) - 'a']);
// 如果到达最远边界，可以划分片段
if (i == end) {
result.add(end - start + 1);
start = i + 1;
}
}
return result;
}
为什么这样做正确？
关键观察：如果字母 a 出现在位置 0 和位置 8，那么包含位置 0 的片段必须延伸到位置 8。所以我们需要追踪每个字母的最后出现位置，确保片段覆盖所有已出现字母的最后位置。
加油站（LeetCode 134）
在一条环路上有 n 个加油站，第 i 个加油站有汽油 gas[i] 升。从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。求从哪个加油站出发能够绕环路行驶一周。
贪心策略：
- 如果总油量小于总消耗，不可能完成
- 从起点开始，如果到达某个站点油量为负，说明从起点到该站点都不可能是起点
- 从下一个站点重新开始尝试
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalGas = 0;
int totalCost = 0;
// 检查总油量是否足够
for (int i = 0; i < gas.length; i++) {
totalGas += gas[i];
totalCost += cost[i];
}
if (totalGas < totalCost) return -1;
int tank = 0; // 当前油箱中的油量
int start = 0; // 起点
for (int i = 0; i < gas.length; i++) {
tank += gas[i] - cost[i];
// 如果油量为负，说明从 start 到 i 都不可能是起点
if (tank < 0) {
start = i + 1; // 从下一个位置重新开始
tank = 0;
}
}
return start;
}
关键洞察：如果从 A 出发，经过 B 时油量变为负，那么从 A 到 B 之间的任何站点出发都不能绕过 B。因为从 A 出发到达 B 之前的任何站点时油量都是正的，如果从中间某点 C 出发，相当于少带了 A 到 C 的油量，更不可能通过 B。
股票买卖 II（LeetCode 122）
给定一个数组表示股票每天的价格，可以买卖多次，求最大利润。
贪心策略：只要明天价格比今天高，就今天买、明天卖。
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
// 如果明天价格更高，就进行买卖
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
为什么连续买卖等价于低买高卖？
考虑价格序列 [1, 2, 3, 4]：
- 低买高卖：1买4卖，利润 = 4 - 1 = 3
- 连续买卖：(2-1) + (3-2) + (4-3) = 1 + 1 + 1 = 3
两者利润相同。贪心策略本质上是把所有上升段累加起来。
零钱兑换问题（注意：贪心不一定正确）
给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少硬币数。
贪心策略：优先使用面额最大的硬币。
这个贪心策略在某些硬币系统下正确（如人民币、美元），但在一般情况下不正确。
反例：硬币面额 [1, 3, 4]，金额 6。
- 贪心：6 = 4 + 1 + 1，需要 3 枚
- 最优：6 = 3 + 3，需要 2 枚
什么时候贪心有效？
当硬币面额满足整除性质时，贪心有效：每个面额是比它小的所有面额的倍数。例如：[1, 5, 10, 25]（美元硬币）。
对于一般情况，需要使用动态规划求解。
// 动态规划解法（适用于所有情况）
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
贪心算法的局限
贪心算法虽然简单高效，但有很大的局限性：
1. 不保证全局最优
贪心算法每步选择局部最优，但局部最优的组合不一定是全局最优。
经典反例：0-1背包问题
背包容量 10，物品：
- A：价值 60，重量 10
- B：价值 50，重量 5
- C：价值 50，重量 5
如果按"价值最大"贪心，选择 A，无法再选择其他物品，总价值 60。 但最优解是选择 B 和 C，总价值 100。
2. 选择标准的确定
贪心算法的关键是选择正确的贪心标准。同样的活动选择问题：
- 按开始时间贪心：错误
- 按结束时间贪心：正确
选择错误的标准会得到错误的结果。
3. 正确性证明困难
贪心算法的实现往往很简单，但证明其正确性可能非常困难。比如 Dijkstra 算法的正确性证明需要较多篇幅。
贪心 vs 其他算法
| 问题类型 | 适用算法 | 原因 |
|---|---|---|
| 活动选择 | 贪心 | 存在贪心选择性质 |
| 0-1背包 | 动态规划 | 子问题重叠，无贪心选择性质 |
| 完全背包 | 动态规划/贪心 | 某些情况下贪心有效 |
| 最短路径 | Dijkstra（贪心） | 非负权重时有贪心选择性质 |
| 最小生成树 | Prim/Kruskal（贪心） | 存在贪心选择性质 |
算法对比
| 指标 | 贪心算法 | 动态规划 | 回溯 |
|---|---|---|---|
| 时间复杂度 | 通常 或 | 通常 或更高 | 通常指数级 |
| 空间复杂度 | 通常 或 | 通常需要表格存储 | 递归栈 |
| 适用范围 | 有限 | 广泛 | 广泛 |
| 实现难度 | 简单 | 中等 | 中等 |
| 正确性证明 | 困难 | 相对简单 | 直接 |
小结
贪心算法的核心要点：
- 适用条件：贪心选择性质 + 最优子结构性质
- 正确性证明：贪心保持领先或交换论证
- 常见贪心策略：
- 区间问题：按结束时间排序
- 跳跃问题：维护最远可达位置
- 分发问题：多次遍历处理不同方向
- 局限性：不保证全局最优，需谨慎使用
贪心算法的优势在于简单高效，但前提是必须满足特定条件。在面对优化问题时，应先判断是否存在贪心选择性质，否则应考虑动态规划等其他方法。
练习
入门：
- LeetCode 455：分发饼干
- LeetCode 122：买卖股票的最佳时机 II
- LeetCode 860：柠檬水找零
进阶： 4. LeetCode 55：跳跃游戏 5. LeetCode 45：跳跃游戏 II 6. LeetCode 435：无重叠区间 7. LeetCode 452：用最少数量的箭引爆气球 8. LeetCode 763：划分字母区间 9. LeetCode 134：加油站 10. LeetCode 135：分发糖果
挑战： 11. LeetCode 406：根据身高重建队列 12. LeetCode 621：任务调度器 13. LeetCode 738：单调递增的数字