贪心算法（Greedy Algorithm）
贪心算法是一种在每一步选择中都采取当前状态下最优（最有利）的选择，从而希望导致全局最优解的算法范式。
定义
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下局部最优的选择，期望通过这种方式达到全局最优的算法思想。
核心本质：贪心算法 = 遍历思维 + 不穷举所有可行解，直接推导最优选择。
核心特性
| 特性 | 说明 |
|---|---|
| 局部最优 | 每一步都选择当前看起来最好的选项 |
| 无回溯 | 做出选择后不撤销，不回头检查 |
| 高效性 | 通常时间复杂度为 O(n) 或 O(1) |
| 适用条件 | 需要满足贪心选择性质和最优子结构 |
贪心选择性质
贪心算法的正确性需要证明贪心选择性质：
通过局部最优选择，能够产生全局最优解。
关键区别：
- 动态规划：穷举所有可行解（去重后），再找最优
- 贪心算法：不穷举，直接选择当前最优，跳过其他可能性
与类似算法对比
| 维度 | 贪心算法 | 动态规划 | 回溯算法 |
|---|---|---|---|
| 穷举范围 | 不穷举所有可行解 | 穷举所有可行解（去重后） | 穷举所有可行解（剪枝后） |
| 优化手段 | 推导最优，直接选择 | 备忘录优化，避免重复计算 | 剪枝优化，提前排除 |
| 时间复杂度 | 通常 O(n) 或 O(1) | 多项式级 O(n²)、O(n³) | 指数级 O(2ⁿ)、O(n!) |
| 正确性保证 | 需要证明贪心选择性质 | 只要满足最优子结构就正确 | 只要正确穷举就保证找到 |
| 状态管理 | 通常不需要回溯 | 需要存储子问题解 | 需要维护路径，做选择/撤销选择 |
演进关系：回溯（剪枝优化）→ 动态规划（备忘录优化）→ 贪心（推导最优，不穷举）
经典问题
| 问题 | 难度 | 贪心策略 |
|---|---|---|
| 跳跃游戏 | 中等 | 维护最远可达位置 |
| 跳跃游戏 II | 中等 | 在不得不跳时再跳 |
| 分发饼干 | 简单 | 小饼干喂小胃口 |
| 无重叠区间 | 中等 | 按结束时间排序，选结束最早的 |
| 用最少数量的箭引爆气球 | 中等 | 按起始位置排序，合并重叠区间 |
| 最优加油策略 | 困难 | 每次没油时，选择经过的加油站中油量最大的 |
解题框架
// 贪心算法通用思路
void greedy(vector<int>& nums) {
// 1. 排序或预处理（根据贪心策略）
sort(nums.begin(), nums.end());
// 2. 遍历，每一步做当前最优选择
for (int i = 0; i < nums.size(); i++) {
// 根据贪心策略做选择
// 不需要回溯，不需要备忘录
}
}
适用条件
贪心算法能正确求解的问题必须满足：
- 贪心选择性质：局部最优选择能导致全局最优解
- 最优子结构：问题的最优解包含子问题的最优解
⚠️ 不是所有问题都适合贪心：如果问题不满足贪心选择性质，贪心算法可能得到错误结果。
经典反例
0-1 背包问题：
- 贪心策略：优先选价值密度（价值/重量）最高的物品
- 错误：可能因为选了高密度物品，导致背包剩余空间无法利用
- 正确解法：动态规划
分数背包问题：
- 贪心策略：优先选价值密度最高的物品
- 正确：因为可以按比例装入，贪心策略正确
时间复杂度
| 问题类型 | 时间复杂度 | 说明 |
|---|---|---|
| 简单贪心 | O(n) | 一次遍历 |
| 需要排序 | O(n log n) | 排序通常是最耗时操作 |
| 复杂贪心 | O(n²) 或更高 | 可能需要多次扫描 |
注意事项
- 必须证明正确性：不能凭直觉使用贪心，需要证明贪心选择性质成立
- 对比动态规划：如果贪心正确性难以证明，考虑使用动态规划
- 从简单例子入手：通过小例子验证贪心策略是否真的能得到最优解
- 关注边界条件：有些问题大部分情况贪心正确，但特定边界会出错
应用场景
- 调度问题：任务调度、区间调度（选择最多不重叠区间）
- 最优路径：Dijkstra 算法（带权重图的最短路径）
- 最小生成树：Prim 算法、Kruskal 算法
- 霍夫曼编码：每次选频率最小的两个节点合并
- 部分背包问题：可以按比例装入物品