0.目录：
1.第一部分：导言 —— 为什么需要贪心算法？
2.第二部分：什么是贪心算法？
3.第三部分：贪心算法的完整使用方法
4.第四部分：贪心算法的常见问题与解决方案
5.第五部分：总结与拓展
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第一部分：导言 —— 为什么需要贪心算法？
在算法设计中，我们常面临两类核心需求：追求最优解（如最少硬币数、最多活动数）和追求高效解（如降低时间复杂度）。传统暴力枚举法虽能遍历所有可能，但面对大规模数据时（如 1E5 级别的元素），会因时间复杂度过高（如O（2N2^N2N ）、O（N！））直接超时，无法实用。
> ·生活中 “找零优先用大面额硬币”“选课优先选早结束的课程”，本质都是贪心策略的应用；
> ·算法竞赛中 “区间覆盖”“哈夫曼编码” 等经典问题，贪心算法是最优解决方案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二部分：什么是贪心算法？
贪心算法的本质是 “短视的最优决策”—— 它不考虑未来步骤的影响，仅在当前状态下选择 “看起来最好” 的选项，通过逐步累积局部最优解，最终期望得到全局最优解。
2.1 贪心算法的底层逻辑
贪心算法的执行依赖 “两步走” 逻辑，缺一不可：
> 1.局部最优选择：每一步都选择当前状态下最优的选项（如 “最大面额硬币”“最早结束活动”），且该选择一旦做出便不可逆；
> 2.问题规模缩减：每完成一次局部选择后，原问题会转化为一个更小的子问题（如找零金额减少、剩余活动范围缩小），重复步骤 1 直到子问题解决。
2.2 贪心 VS 暴力枚举：核心优势对比
特性 暴力枚举 贪心算法 决策逻辑 枚举所有活动组合，筛选不冲突的最大集合 每步选最早结束的活动，逐步筛选 时间复杂度 O（2n2^n2n）（n=10 时为 1024 次计算） O (nlogn)（排序占主导，n=10 时仅需 30 次左右计算） 空间复杂度 O (n)（存储所有组合） O (1)（仅存储当前选择状态） 实用性 仅适用于 n≤20 的小规模问题 支持 n=1e5 的大规模问题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三部分：贪心算法的完整使用方法
3.1 前置准备：明确贪心算法的适用条件
并非所有问题都能使用贪心算法，必须满足以下两个核心性质，否则局部最优的累积会导致全局次优：
性质 1：贪心选择性质
每一步的局部最优选择，必然能导向全局最优解
可通过 “反证法” 验证：假设某一步不选局部最优选项，而选择其他选项，最终得到的全局解会比选局部最优时更差。
例如 “活动选择问题”：若某一步不选最早结束的活动 A，而选结束更晚的活动 B，那么 B 会占用更多后续时间，导致能选择的总活动数减少，全局解更差。
性质 2：最优子结构
全局最优解包含其子问题的最优解。
即问题的最优解可以拆分为多个子问题的最优解，且子问题的最优解可独立求解。
例如 “钱币找零问题”（适合贪心的面额体系）：凑出金额 186 元的最优解（100+50+20+10+5+1），包含凑出 86 元的最优解（50+20+10+5+1），而 86 元的最优解又包含 36 元的最优解（20+10+5+1），以此类推。
3.2 贪心算法的 4 步核心流程
使用贪心算法解决任何问题，都可遵循固定流程，核心是 “确定贪心策略”：
> 1.问题拆解：将原问题拆分为多个连续的子问题（如 “凑 186 元” 拆分为 “先选最大面额，再凑剩余金额”）；
> 2.定义贪心策略：明确 “什么是当前子问题的局部最优选择”（如 “优先选最大面额硬币”“优先选最早结束活动”）；
> 3.执行局部选择：按策略做出当前选择，更新问题状态（如减少待凑金额、更新已覆盖时间范围），缩小问题规模；
> 4.验证全局最优：（可选）通过数学归纳法或反证法证明，所有局部最优选择的累积结果即为全局最优（竞赛中若问题经典可省略）。
3.3 经典问题实战：2 类高频场景
场景 1：活动选择问题（最多参加活动数）
问题描述
给定 N 个活动，每个活动有开始时间 START[I] 和结束时间 END[I]，同一时间只能参加一个活动，求最多能参加的活动数量。
贪心策略
优先选择 “最早结束” 的活动—— 最早结束的活动能留下最多时间给后续活动，是局部最优选择。
AC代码：
关键细节解析
> ·排序的必要性：若不排序，无法快速找到 “最早结束的活动”，会导致局部选择错误；
场景 2：钱币找零问题（最少硬币数）
问题描述
给定一套硬币面额（如 1、5、10、20、50、100），以及一个目标金额，每种硬币数量无限，求凑出目标金额所需的最少硬币数（假设面额体系适合贪心）。
贪心策略
优先选择 “面额最大” 的硬币—— 大面额硬币能快速减少待凑金额，减少总硬币数，是局部最优选择。
AC代码：
关键细节解析
> ·面额体系的限制：贪心仅适用于 “每一面额都能被更小面额组合覆盖” 的体系（如人民币、美元），若面额为 {1,3,4}，凑 6 元时贪心会选 4+1+1（3 枚），而最优解是 3+3（2 枚），此时需改用动态规划；
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第四部分：贪心算法的常见问题与解决方案
4.1 问题 1：如何判断问题是否适合贪心？
解决方案：通过 “反证法”+“样例测试” 验证：
> 1.假设某一步不选局部最优选项，看是否能得到更优的全局解；
> 2.构造多个测试样例（尤其是边界情况，如金额为 0、区间无重叠），验证贪心结果是否与最优解一致。
4.2 问题 2：贪心策略不唯一时如何选择？
解决方案：根据问题目标确定策略方向：
> ·若目标是 “最大化数量”（如活动选择），通常优先选 “占用资源少” 的选项（如早结束、短时长）；
> ·若目标是 “最小化数量”（如找零、区间覆盖），通常优先选 “贡献资源多” 的选项（如大面额、广覆盖）。
4.3 问题 3：贪心结果不是最优时怎么办？
解决方案：改用其他算法，常见替代方案：
> ·动态规划：适用于不满足贪心选择性质，但存在最优子结构的问题（如 {1,3,4} 面额的找零问题）；
> ·回溯法：适用于小规模问题，需枚举所有可能解（如小规模的区间选择问题）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第五部分：总结与拓展
5.1 贪心算法的核心优势与局限
优势 局限 时间复杂度低（多为 O (nlogn)），适合大规模数据 仅适用于满足 “贪心选择性质” 和 “最优子结构” 的问题 逻辑直观，代码实现简单 无法回溯，一步错则全局错（需严格验证策略） 空间复杂度低（多为 O (1) 或 O (n)） 部分问题需结合排序，排序效率影响整体性能
5.2 拓展学习：进阶贪心问题
> ·哈夫曼编码：通过贪心选择 “频率最低的两个节点” 构建最优前缀编码，用于数据压缩；
> ·任务调度问题：优先调度 “剩余次数最多” 的任务，最小化总调度时间；
> · FRACTIONAL 背包问题 ：优先选择 “单位价值最高” 的物品，最大化背包总价值（与 0-1 背包区分，0-1 背包需用动态规划）。
通过大量实战练习（如 LEETCODE 贪心标签题），可快速提升 “定义贪心策略” 的能力，在算法竞赛和工程问题中灵活应用。
创作不易，给一个赞吧，求求了！
@AC君快给我加精
