贪心算法从0到1完全指南（含LeetCode Top100考题解析）

一、贪心算法理论基础（0基础入门）

1. 贪心算法的核心定义

贪心算法的本质是通过每一步选择局部最优解，最终堆叠出全局最优解。它不追求全局最优的推导过程，而是基于当前阶段的最优选择，逐步逼近最终目标。

举个通俗例子：从一堆不同面额的钞票中取10张，要得到最大金额，每次选当前剩下的最大面额钞票（局部最优），最终总和就是最大金额（全局最优）。但需注意，贪心并非万能——若用“选最大盒子装满背包”的思路，可能无法达到最优解（此时需动态规划）。

2. 贪心算法的适用场景

贪心没有固定套路，核心判断标准：

• 手动模拟局部最优策略，能推出全局最优，且找不出反例；
• 问题可拆分为独立的子问题，每个子问题的最优解能累积为全局最优；
• 常见适用场景：区间问题（合并、覆盖、去重）、资源分配、序列构造等。

3. 贪心算法的解题步骤（简化版）

无需拘泥于复杂理论，核心三步：

1. 拆分问题：将原问题拆解为多个独立的子问题；
2. 确定局部最优策略：明确每个子问题的最优选择标准（如“选最大”“选最早结束”）；
3. 累积最优解：将所有子问题的局部最优解合并，得到全局最优。

4. 贪心与其他算法的区别

二、LeetCode Top100贪心算法核心考题（分类解析）

（一）基础入门题（常识性贪心，难度★★☆）

1. 分发饼干（LeetCode 455）

• 题目描述：每个孩子有胃口值g[i]，每块饼干有尺寸s[j]，s[j]≥g[i]时可满足孩子。求最多满足的孩子数。
• 局部最优：大饼干优先满足大胃口孩子（避免小饼干浪费）；
• 解题步骤：
  1. 对g和s排序（从小到大或从大到小）；
  2. 从后向前遍历胃口数组，用大饼干匹配大胃口；
• 代码片段：

intfindContentChildren(vector<int>&g,vector<int>&s){sort(g.begin(),g.end());sort(s.begin(),s.end());intindex=s.size()-1,res=0;for(inti=g.size()-1;i>=0;--i){if(index>=0&&s[index]>=g[i]){res++;index--;}}returnres;}

2. K次取反后最大化的数组和（LeetCode 1005）

• 题目描述：对数组元素执行K次取反操作，求最终最大数组和。
• 局部最优：
  1. 先将绝对值大的负数取反（转化为正数，提升总和）；
  2. 若K剩余为奇数，取反最小的正数（损失最小）；
• 代码片段：

staticboolcmp(inta,intb){returnabs(a)>abs(b);}intlargestSumAfterKNegations(vector<int>&A,intK){sort(A.begin(),A.end(),cmp);for(inti=0;i<A.size()&&K>0;++i){if(A[i]<0){A[i]*=-1;K--;}}if(K%2==1)A.back()*=-1;returnaccumulate(A.begin(),A.end(),0);}

3. 柠檬水找零（LeetCode 860）

• 题目描述：柠檬水售价5美元，顾客支付5/10/20美元，需正确找零（初始无零钱）。
• 局部最优：收到20美元时，优先用10+5找零（5美元更万能，可用于10和20美元找零）；
• 代码片段：

boollemonadeChange(vector<int>&bills){intfive=0,ten=0;for(intbill:bills){if(bill==5)five++;elseif(bill==10){five--;ten++;}else{// 20美元if(ten>0&&five>0){ten--;five--;}elsefive-=3;}if(five<0)returnfalse;}returntrue;}

（二）序列问题（贪心策略+细节处理，难度★★★）

1. 摆动序列（LeetCode 376）

• 题目描述：连续数字的差严格正负交替为摆动序列，求最长摆动子序列长度（可删除元素）。
• 局部最优：删除单调坡度上的中间节点（保留两端峰值，增加摆动次数）；
• 关键细节：处理平坡（如[1,2,2,2,1]）和首尾节点；
• 代码片段：