作为常年在算法题和工程代码之间反复横跳的人，我越来越觉得贪心算法是最接近“现实决策”的一类算法。它在C++里的落地，不只是背几个模板题，而是训练一种观察问题的角度：局部最优能不能推出全局最优，怎么证明，怎么用代码稳稳地把它实现出来。这篇东西不是教科书式的知识罗列，我想从实际做题、写C++代码、以及日常工程中踩过的坑出发，把贪心算法这条线的核心逻辑讲透，顺便把C++实现里的细节也交代清楚。
文章适合几类人：刚学完C++语法、准备开始啃算法的初学者；正在准备笔试面试、想在短时间内把贪心题型的套路摸清楚的求职者；以及工作中经常要做调度、排程、资源分配、删减数据等“效果最优”决策的开发者。我尽量不堆砌概念，而是把每一道经典题的思考过程、代码写法、推导方式拆开给你看。
1. 贪心算法到底在“贪”什么
1.1 核心思想：每一步都做当下最好的选择
贪心算法的中文名字起得非常直白：贪。它不让你的程序在全局范围内搜索全部状态，而是每走一步，都只挑当前看起来最优的那个选项，然后一路走下去。
听起来很像“走一步看一步”，所以很多人第一印象是它太莽撞。其实贪心能成立，靠的是问题本身具有两个性质：贪心选择性质和最优子结构。前者是说，你能通过一系列局部最优的选择拼出全局最优解；后者是说，问题的最优解里包含着子问题的最优解。只有这两个条件都满足，贪心算法才是正确的。
我用生活里的事来解释：你去餐厅点菜，如果菜单上每道菜的价格都是固定的，你想在预算内尽量多吃几道不同的菜，那最合理的做法是先把贵的菜挑出来？不对，是先看便宜的，因为便宜菜的数量多。这就是一个典型的贪心策略。但如果菜单有“套餐优惠”“满减”，便宜的菜可能不是最优，因为组合起来可能更亏，这时候贪心就不一定对，得考虑别的方案。
C++里写贪心，结果不等于思路，思路再清晰，代码里如果排序规则写错、边界没处理干净、数据类型选小了，一个字符的差异就能让整题全错。所以学贪心，绝对不只是学“套路”，还要学怎么把策略精确翻译成代码。
1.2 贪心选择性质：局部最优如何通向全局最优
怎么判断一个局部最优的选择，最后一定能组成全局最优？最常见的方法是“交换论证法”。
假设你按某个规则选了一个局部最优解，如果最终的全避最优解和你选的这个局部解不一样，你就去证明这个“不一样”可以被一次交换修正过来，而且修正后结果不会变差。反复交换，最终能证明你的贪心选择和某个全局最优解“兼容”。
举例来说，活动选择问题里，你按结束时间最早来选活动，如果最优解的第一个活动不是最早结束的那个，那这个活动一定结束得比贪心选的更晚，把它换成最早结束的那个，后续活动照样可以安排，不会冲突。这样一次一次交换，贪心策略就等价于某个最优解。
我用C++写活动安排时，代码其实很短：
#include <bits/stdc++.h> using namespace std; struct Activity { int start, end; }; bool cmp(const Activity &a, const Activity &b) { return a.end < b.end; // 按结束时间升序 } int main() { int n; cin >> n; vector<Activity> act(n); for (int i = 0; i < n; ++i) { cin >> act[i].start >> act[i].end; } sort(act.begin(), act.end(), cmp); int ans = 0, lastEnd = 0; for (const auto &a : act) { if (a.start >= lastEnd) { // 只有不重叠才选 ++ans; lastEnd = a.end; } } cout << ans << endl; return 0; }这里排序是核心，按结束时间提前排好，后面一遍扫描就完成选择。这就是贪心的典型发力方式：先用排序把“全局顺序”整理好，再线性扫描做决策。后面讲到的删数问题、区间覆盖、拼接最大数，本质上全都是这个模式。
1.3 和动态规划的分界线在哪
很多初学者最困惑的就是：什么时候用贪心，什么时候用动态规划？傻傻分不清。
有一个朴素的判别标准：如果每一个决策做完之后，子问题形状没有改变，状态空间不会膨胀，那大概率可以试试贪心；如果决策之后至少产生两个不同的子问题，而且需要分别求解并比较才能拿到解，那通常得用动态规划。
举一个对比：零钱兑换问题，如果硬币面额是1、5、11，要找15元，贪心做是“先拿最大面额”，拿一个11，再拿四个1，总共5枚。但最优是三个5，一共3枚。贪心在这里就错了，因为拿走11之后，剩下4块钱的子问题已经和全局不可分割地连锁起来了，需要动态规划去处理。
但如果是找硬币的“硬币数量百分比”题，或删数问题，每个决策都只影响一个连续序列，且剩余问题的结构和原问题完全一致，贪心就成立。判断贪心是否有效，最好的办法是拿动态规划做对照，跑小数据量，看两种方案结果是否一致。这个验证手段我后面会专门细讲。
2. 手把手拆解两个入门必做经典题
2.1 删数问题：一个最容易写错的贪心
“删数问题”几乎是每个学贪心的人都会遇到的题。题目描述通常是：给出一个由数字组成的字符串，删掉其中k个数，让剩下的数字按原顺序组成的数尽可能小。
比如1432219，删掉3个数字，能得到的最小数字是1219。
这个题的贪心策略是：从左到右扫描，如果发现当前数字比后一个数字大，那么为了把数字变小，就应该“删掉”这个当前数字。反复操作，直到删除次数用完。如果一轮扫下来还没删够，再把末尾最大的数字删掉。
为什么这个策略是对的？因为高位数字对整个数值的影响远大于低位。从左到右第一次出现“下降沿”的位置，比如143里的4和3，那个高位4已经比后面的3大了，高位大、低位小，那为了让结果尽量小，删掉4肯定比删掉3更划算。继续在剩余的序列里重复这个过程，最终就能得到字典序最小的结果。
但是在代码实现里，这个题有好几个经典坑：
- 误用
bool标记删除位置，导致后续处理混乱； - 越界访问
s[i + 1]； - 忘记处理删除完以后前面的
0； - 如果k等于字符串长度，忘记返回
"0"。
我在C++里一般用一个栈来模拟：“维护一个逐渐变小的单调栈”。
string removeKDigits(string num, int k) { string res; // 用string模拟栈 for (char c : num) { while (!res.empty() && k > 0 && res.back() > c) { res.pop_back(); // 高位比低位大，坚决删掉 --k; } res.push_back(c); } // 如果还有没删完的，从尾部删掉大的数字 while (k > 0 && !res.empty()) { res.pop_back(); --k; } // 去掉前导0，但至少要保留一位 int pos = 0; while (pos < res.size() && res[pos] == '0') { ++pos; } res = res.substr(pos); return res.empty() ? "0" : res; }这个代码的巧妙之处在于，用res的尾部作为“当前位置”，每次新数字进来，就和前面的比，一旦形成逆序，就弹出。整个过程只扫一遍，时间复杂度是O(n)。
我当时的教训是：一开始我想用vector<char>来模拟，其实没必要，标准库的string本身就是动态数组，push_back、pop_back、back这些操作全都有，可以直接当栈用。能少引入一个容器，代码更干净。
2.2 删数问题背后的贪心证明
光会写代码不够，面试和复盘的时候还得能说出“为什么这么删是对”的理据。
删数问题的交换论证比较直观。假设在某个位置出现了res.back() > c这种情况，我们可以想象一个最优答案。如果最优答案里保留了res.back()这个高位数字，而删的是后面某个更低位的数字，那么把这两个操作交换一下，也就是删掉高位数字、保留低位数字，结果只会更小，而后续数字的顺序不变。通过这样的交换，我们总能让最优解符合贪心策略的每一步，所以贪心正确。
这个证明过程，比代码本身更能体现“为什么学贪心”的意义。工程中很多看似合理的策略，都值得在脑子里这样“过一遍证明”，防止凭感觉上线之后出大问题。
2.3 区间调度：把“贪心排序”用到熟
区间调度类和删数问题的思路是一脉相承的：先排序，再扫描。
最典型的题是：给n个会议的开始时间和结束时间，问最多能参加多少个不重叠的会议。策略是按结束时间从小到大排，然后只要当前会议的开始时间不早于上一个选中会议的结束时间，就选它。
这个策略背后的直觉是：把结束时间早的会议留出来，能给后面的会议腾出更多的时间缝隙，所以“局部最紧凑”的选择能带来“全局最多”的数量。
int maxMeetings(vector<pair<int, int>>& meetings) { sort(meetings.begin(), meetings.end(), [](const pair<int, int>& a, const pair<int, int>& b) { return a.second < b.second; }); int cnt = 0, lastEnd = 0; for (auto &m : meetings) { if (m.first >= lastEnd) { ++cnt; lastEnd = m.second; } } return cnt; }这里我特别强调一下C++中lambda的排序写法。[](const pair<int,int>& a, const pair<int,int>& b)里的[ ]是捕获列表，不捕获外部变量就留空，在写竞赛和面试代码时，这种匿名lambda比单独写一个全局比较函数更紧凑，也不会污染命名空间。
但lambda有个坑：如果你在里面用了外部变量，比如offset，一定要写[&]或者[=]，否则编译报错。如果你的comp函数是一个类成员函数，排序的时候不能直接传成员函数指针，得在外面套一层静态函数或者lambda。这些细节看起来和算法无关，却真的是我在写C++贪心代码时经常被打断的原因。
3. C++里实现贪心的实用技巧
3.1 排序相关：sort、stable_sort和自定义比较器
贪心算法最依赖的操作就是排序。C++的标准库sort排序是不稳定的，而stable_sort能保持相等元素的原有相对顺序。有些贪心题里“相等时谁先谁后”很关键，比如拼接数字求最大，如果两个数字构成的组合一样，它们谁在前结果都不变，那用哪个都行。但如果题目要求按原顺序优先保留某个字段，最好想清楚要不要用stable_sort。
自定义比较器时要注意严格弱序。比较器的返回值描述的是“a是否应该排在b前面”，如果a和b相等，必须返回false，而且在比较中不能让a < b和b < a同时为真。我曾经在写双关键字排序时，把“按结束时间升序，时间相同按开始时间降序”写成了两次比较，导致sort结果乱跳。原因就是没有保证严格弱序。
举一个实际例子，区间覆盖问题：给一些区间，问最少用几个区间能覆盖一个目标区间。这个题要先按开始时间升序，开始时间相同时按结束时间降序。为什么？因为同样是起点，能覆盖到更远的区间更优，后续就能用更少的区间补上剩余部分。这个排序策略如果反了，可能一整个贪心判断逻辑就崩了。
3.2 优先队列：动态取“当前最优”的利器
不是所有贪心都靠数组排序解决，有些问题的“当前最优”会随着处理过程不断变化，这时候优先队列（priority_queue）就是首选。
比如合并果子问题：每次从一堆果子里挑两个重量最小的合并，合并完了再放回去，问最小总耗费。如果每次都用排序重新找最小，复杂度太高，正确做法是用小顶堆，每次弹出两个最小值，合并后压回去。
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆 for (int x : nums) pq.push(x); int ans = 0; while (pq.size() > 1) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); int sum = a + b; ans += sum; pq.push(sum); }这里的类型写法是C++新手很容易忘的：priority_queue<int, vector<int>, greater<int>>，默认情况下priority_queue<int>是大顶堆，想变成小顶堆必须写完整的三段式。如果你觉得这个写法太啰嗦，也可以直接存入负数，用小技巧翻转大小关系，但代码可读性会下降，我一般不用。
类似要用到优先队列的场景还包括：每次取最大最小值、每次合并K个有序链表、哈夫曼编码等。形式不一，本质都是“从动态变化的集合里反复提取最值”。
3.3 结构体、tuple和pair的使用选择
贪心题的排序对象，经常是一个含有多个属性的事物。我建议优先用pair或tuple，只有属性超过三到四个的时候再写结构体。太早写结构体会让代码整体看起来重量级。
pair<int,int>默认先按first排，再按second排。如果我自己定义了lambda比较器，其实底层的存储方式无所谓。但是在竞赛环境里，用pair可以减少不少代码量，因为make_pair或者直接用花括号{}初始化都很方便。
我记得有一次比较器的第二个排序维度写反了，导致题目的样例都过不去，排查了半天。后来我改成给结构体加上operator<重载，再配合sort，逻辑一下子就清楚了。结构体写清楚的好处是，几个字段都有名字，读代码的时候不需要记“first到底代表开始时间还是结束时间”。
3.4 返回值和边界条件设计的工程习惯
贪心题普遍爱考边界：空数组、单个元素、k等于长度、全是0、溢出。我在写代码时习惯在函数入口做一层前置检查，优先保证数据合法性，再进入贪心循环。
if (num.empty() || k <= 0) return num; if (k >= num.size()) return "0";这种防御式写法在竞赛里也许显得略啰嗦，但在工作中是标配。很多crash都发生在边界条件被忽略的时候。C++的vector越界不会自动报错，string的back()在空串上调用是未定义行为，这些隐形的雷区都需要我们对边界有足够敏感。
4. 常见陷阱与实战踩坑记录
4.1 容易栽坑的排序规则
我在指导别人写贪心题的时候发现，90%的人第一次提交出错，问题都出在排序上。
举一个非常经典的反直觉题：给定一组数字，把它们按顺序拼成一个最大的数。比如[3, 30, 34, 5, 9]，正确答案是9534330。
如果按普通字典序排，9最大，5次之，34和3谁在前？直观上3比34小，但3拼在34后面组成343，而34拼在3后面组成343，不行，得换个例子，3和32，332和323，明显3应该在32前面。
正确的比较方式是自定义：比较a + b这个字符串和b + a这个字符串，谁大谁就排前面。写成lambda就是：
sort(nums.begin(), nums.end(), [](const int &a, const int &b) { string sa = to_string(a), sb = to_string(b); return sa + sb > sb + sa; });这个细节是纯字典序解决不了的，它会直接决定答案对错。所以碰到字符串拼接型问题，千万别偷懒直接对整数排序。
这个问题的实质是：贪心的“局部最优比较”本身就要自定义，不能指望C++默认比较规则恰好契合题意。
4.2 相等元素和保留顺序的问题
之前提到过stable_sort，在很多贪心题里，排序只决定“优先级”，并不要求改变相等元素的相对位置。如果你用的是sort，那是快速排序的混合排序实现，不保证稳定性；如果题目要求量化比较之外还保留初始顺序，请自觉用stable_sort。
比如任务调度类问题中，两个任务优先级完全一样，但一个先出现在原数组里，题目要求输出结果保持原顺序，此时stable_sort就比sort更合适。贪心算法只决定选择策略，要不要打破原顺序，是另一层需求，别混在一起处理。
4.3 整数溢出与类型选择
贪心题常常涉及对大量元素求和、求积。C++的int通常是32位，最大值约21亿。当数据规模是10^5、每项是10^5时，乘积很容易爆int。如果你还在用int做累加，最后答案错都不知道错在哪。
一个比较常用的习惯是：涉及累计和、累计差、最大值最小值比较时，直接使用long long（64位）作为计算类型，它能容纳到9.2×10^18，绝大多数贪心题都能镇住。
另一个隐蔽问题是：priority_queue里的元素类型如果和累加变量类型不一致，可能出现隐式转换导致溢出。比如堆里存int，但是累加结果用long long，依然可能在堆内相加时先按int计算再转。稳妥做法是从一开始就用long long存数。
我自己有一次写区间覆盖的变体题，区间长度最大能到10^9，我用int存开始和结束时间，结果两段长度相加时直接变成负数，排序立刻错乱。排查一个小时后才发现，修改成long long之后瞬间通过。这个经验让我在之后所有的贪心题里养成了“能用long long绝不用int”的习惯。
4.4 模拟重复删除或重复选择导致超时
初学删数问题时，有人会写两层循环：外层每删一个数就重新扫描整个字符串。字符串长度是10^5，k也是10^5，这就是O(n^2)的复杂度，直接TLE。
优化方向就是之前提到的栈思路，一次扫描完成所有“删除”动作。贪心算法的精彩不只在于“策略正确”，还在于“执行高效”。同样是贪心，盲写和用正确数据结构实现的代码，耗时差异可能是天壤之别。
5. 验证贪心解法的几种可靠手段
5.1 先用小规模数据做对照
当我不确定一个贪心策略对不对时，我会写一个暴力解法或动态规划解法，用于小数据量（比如n<=10）的情况下做对照验证。暴力永远是对的，因为它在正确性上做了穷举。
以删数问题为例，小于等于10个数字时，用DFS枚举所有删法，取最小值，再去和贪心解法比对。如果所有随机样例一致，说明贪心大概率正确；如果发现不一致，正好可以把那个反例拿出来分析，看看贪心缺了什么条件。
这种验证思路在竞赛训练里非常高效，因为不等你证明，直接跑几十组随机数据就能把错误暴露出来。而在工程里，它相当于用回归测试去验证你的策略是不是真的按预期执行。
5.2 尝试反证和交换论证
如果随机测试都过了，我还想从理论上再给自己一次交代。通常做两种推理：
- 反证法：假设贪心策略给出的解不是最优解，那么一定存在一个更优解，从这个更优解出发，找出能不能通过一次“局部修正”把它变成贪心解而不变差。如果能，那就证明贪心解是最优。
- 归纳法：考虑规模为n的情况，假设n-1时贪心正确，证明n时贪心选择能保留一个最优解的“前序状态”，然后递归成立。
大多数教材和题解用的都是这两种论证。哪怕你觉得证明是形式化的“标配”，我也建议至少在自己脑子里走一遍完整流程，这样面对面试官追问的时候不会露怯。
5.3 极端值和手工推导
最好手动设计边界测试用例，比随机测试更有针对性。比如删数问题，我会专门测试：
- 数字串全是
0，删除任意k个； - 数字串是递增序列，比如
123456，此时不需要删“下降沿”，只能删末尾； - 数字串是递减序列，比如
54321，此时应该从头部删； - k等于字符串长度；
- 字符串长度为1，k为1。
每次设计用例前，我会先在纸上手算一遍预期结果，再跑代码，防止测试用例本身也是错的。这种习惯在真实项目中相当于“先定期望，再写断言”，能有效防止用错误用例把代码验证成假通过。
6. 实战中的一些“非算法”经验
6.1 从一道题扩展到一类题的建模方式
我发现贪心题看似千变万化，实际建模是可以套路化的：
- 第一步：明确目标函数，是让某个值最大、最小，还是让数量最多、最省。
- 第二步：找“局部变量”：什么事情做完以后，不会牵一发而动全身，可以当作单独决策。
- 第三步：确定决策规则，并试着用交换论证证明它。
- 第四步：选择数据结构：排序、堆、双端队列、栈、线段树，哪个能在当前局面高效地获取局部最优。
- 第五步：处理边界：零输入、巨大输入、相等输入等。
把这套流程在五道题上各跑十遍，你基本就能形成自己的“贪心直觉”，比死记硬背几十道题来得更可靠。
6.2 用C++写贪心时的调试习惯
我调试贪心题的顺序一般是：
- 加装断言，检查排序后是否严格按预期序列排列；
- 对未排序前和排序后的状态打log；
- 写一个短小的暴力解在小样本上对拍；
- 如果答案是错的，先检查类型和边界，再检查比较逻辑，最后检查算法本身。
有几次我自己调试时发现，问题根本不是贪心策略错，而是我在定义比较器时用了引用绑定到临时变量，导致比较结果不稳定。这样的小细节，如果你没有良好的调试顺序，会浪费大量的时间。
所以我在代码里往往会专门抽一个printVector函数，在关键步骤输出当前状态。C++的调试不如Python那么方便，适当打印能在关键时刻救你一命。
6.3 工程中贪心的实际落地
很多人误以为贪心只在算法竞赛中有用，其实工程里的资源分配、缓存淘汰（LRU的变种）、任务优先调度、网页推荐排序、广告流量分配等场景都在用贪心思想。
比如广告预算分配场景里，多个广告位、多个出价方、有限预算，选择哪个广告组合能让整体收益最大化，如果约束足够简单，完全可以用贪心：按单位成本的收益排序，从高到低分配。工程实现时还要考虑响应时间，这时贪心算法因为只需要一次排序加一次扫描，性能非常稳定，很适合在线服务场景。
C++在工程中的优势是高性能和可控的内存布局，加上标准库里的排序、堆、贪心配合起来，写出的调度系统可以在单机承载很大的数据量。这也是为什么我建议做后端和基础架构的同学也把贪心玩熟。
7. 由浅入深：怎么安排自己的练习节奏
如果你是从零开始，我的建议是先完成下面这几组：
第一梯队：删数问题、活动选择、跳跃游戏、康复区间找零（如果硬币罚特殊就换题）。目的是理解基础扫描+排序。
第二梯队：区间覆盖、合并果子、任务调度、拼接最大数。这些题开始引入复杂的排序规则和堆。
第三梯队：哈夫曼编码、K次取反后最大化的数组和、分发糖果、加油站。这些题需要更多思维转化。
第四梯队：贪心+动态规划混合题、贪心失败题。后者很重要，能帮你理解贪心的边界。
训练过程中，我强烈推荐用“同一道题写两种解法”的方式提升：一种是最朴素的暴力，一种是贪心。用暴力检验贪心，再用贪心的复杂度优势去挑战更大的数据范围。这样做题，一个题消化三层，比盲刷五十道题有用得多。
很多同学问C++写贪心要不要背模板，我觉得不用，但常用的几个框架可以滚瓜烂熟：sort+ 单指针扫描的框架，priority_queue的take-smallest框架，以及用string当栈的框架。把这几个框架印在脑子里，绝大多数贪心题都能很快找到切入点。
8. 最后再分享几个我个人的习惯
我在实际写C++贪心代码时，有一个坚持了很久的习惯：把排序规则抽成独立的命名函数。虽然lambda写起来很快，但如果排序规则有15行以上，嵌套在sort调用里会显得很臃肿，且不方便做单元测试。我会单独定义：
bool compareByEndTime(const Activity &a, const Activity &b) { if (a.end != b.end) return a.end < b.end; return a.start > b.start; }这样调试的时候可以直接打印某几个元素的比较结果。工程上这叫“可测试性”，竞赛上这叫“方便调错”，反正都是适合自己的好习惯。
另外，我很少直接用#include <bits/stdc++.h>以外的方式写竞赛代码，但在工作项目里几乎不用这个头文件，会逐个包含需要的标准库头文件。这个问题不算算法问题，但如果你把竞赛代码搬进生产环境，可能会带来编译隐患，务必心里有数。
最后再分享一个小技巧：训练时把每一道贪心题的“策略一句话”写在注释里。比如：
// 删数：从左到右，删除第一个比右侧更大的数 // 活动：按结束时间升序，能选就选 // 合并果子：每次取最小的两个合并别小看这一行注释，它在复盘时能帮你迅速定位“当时是怎么想的”。我翻自己半年后的代码时，经常靠这种注释快速回忆起整个决策过程。
贪心算法的学习，其实是锻炼一种“把直觉用逻辑固定下来”的能力。C++只是载体，真正有价值的，是你学会在每一个决策面前停下来问一句：这一步的局部最优，真的能得到全局最优吗？用代码验证它，用证明说服自己，这个过程练到位了，后续再看动态规划、图论算法，你都会有更强的底气。
