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

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

1. 贪心算法的核心定义

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

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

2. 贪心算法的适用场景

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

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

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

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

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

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

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

1. 分发饼干（LeetCode 455）

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

int findContentChildren(vector<int>& g, vector<int>& s) {

sort(g.begin(), g.end());
sort(s.begin(), s.end());
int index = s.size() – 1, res = 0;
for (int i = g.size() – 1; i >= 0; —i) {

if (index >= 0 && s[index] >= g[i]) {

res++;
index—;
}
}
return res;
}

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

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

static bool cmp(int a, int b) {

return abs(a) > abs(b); }
int largestSumAfterKNegations(vector<int>& A, int K) {

sort(A.begin(), A.end(), cmp);
for (int i = 0; i < A.size() && K > 0; ++i) {

if (A[i] < 0) {

A[i] *= –1;
K—;
}
}
if (K % 2 == 1) A.back() *= –1;
return accumulate(A.begin(), A.end(), 0);
}

3. 柠檬水找零（LeetCode 860）

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

bool lemonadeChange(vector<int>& bills) {

int five = 0, ten = 0;
for (int bill : bills) {

if (bill == 5) five++;
else if (bill == 10) {

five—; ten++; }
else {

// 20美元
if (ten > 0 && five > 0) {

ten—; five—; }
else five -= 3;
}
if (five < 0) return false;
}
return true;
}

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

1. 摆动序列（LeetCode 376）

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