小时候做数学应用题老师总说“你挑最省事的办法试试”长大以后刷算法题发现最省事的办法居然成了一门正经学问这就是贪心。贪心的难点从来不是“想到某个策略”而是“怎么确定这个策略真的对”。这篇内容围绕区间问题、Huffman树、排序不等式、绝对值不等式、推公式这五大经典专题展开覆盖了算法竞赛和面试笔试里最常考的贪心模型适合学完基础数据结构、正准备系统刷贪心题的同学也适合想补证明思路的进阶选手。我会把每个专题的直观想法、严谨证明、代码实现和踩坑点都拆开讲清楚争取让读完的人不仅能做题还能自己判断“什么时候可以贪”。1. 贪心的底层逻辑为什么“局部最优”有时候就是全局最优1.1 贪心不是瞎猜而是有结构的决策贪心的定义听起来很朴实每一步都做当前看起来最好的选择最后凑出全局最优解。但问题在于很多题“看起来最好的选择”根本带不来全局最优比如0-1背包就不能贪心按单位重量价值排序选物品会得到错误答案。所以贪心真正要解决的核心问题是什么样的题可以贪我的理解是贪心能成立的两个关键性质是“最优子结构”和“无后效性”。最优子结构指大问题的最优解包含小问题的最优解无后效性指当前决策只会影响后续状态不会反过来改变已经做出的决策。只要题目同时满足这两点贪心通常就是可行的。但实际做题时不太可能严格验证这两条更实用的方法是先猜一个策略再尝试用数学证明它或者找一个反例把它干掉。1.2 两种最常用的证明武器竞赛圈里最常用的贪心证明方法有两种交换论证exchange argument和反证法。交换论证的思路很像冒泡排序里的“交换相邻元素”假设最优解里的某两个相邻元素顺序和贪心策略给出的顺序不一致如果能证明交换这两个元素后答案不会变差那么把最优解逐步交换成贪心解就能说明贪心解也是最优的。这个方法在排序不等式、推公式题里几乎是万能钥匙。反证法则更直接假设贪心不是最优推出矛盾。比如区间选点里如果最优解的点数少于贪心解就一定能找到一个区间没被覆盖矛盾。还有一个我个人的经验贪心判断策略对错最忌讳的是只跑几个样例就下结论。你随便构造一个特殊用例可能就把它打爆了但构造“能够打爆错误贪心”的用例本身也是一种能力这需要你对题目结构有足够理解。所以我在做贪心题时会逼自己先写一版证明草稿哪怕只有两三行想明白了再写代码这样反而省时间。2. 区间问题四件套选点、分组、覆盖、最大不相交区间问题是贪心最集中的出题区而且它们长得都差不多很容易混。我按自己的记忆方法把它们分成四类区间选点、最大不相交区间数量、区间分组、区间覆盖。前两个是一对“孪生兄弟”后面两个各有各的套路。2.1 区间选点和最大不相交区间数量同一套贪心策略区间选点的题目描述是给定N个闭区间[a_i, b_i]在数轴上选尽量少的点使得每个区间内至少包含一个选出的点。经典做法是把所有区间按右端点从小到大排序然后从前往后扫描每次取当前区间的右端点作为一个“选定点”同时把所有左端点小于等于这个右端点的区间都标记为“已经覆盖”直到遇到一个左端点大于当前右端点的区间再取它的右端点重复这个过程。用C实现大概是struct Range { int l, r; bool operator (const Range W) const { return r W.r; } }; int main() { // 读入n和所有区间 sort(ranges, ranges n); int res 0, last -2e9; for (int i 0; i n; i) { if (ranges[i].l last) { res; last ranges[i].r; } } cout res endl; }为什么按右端点排序而不是左端点因为对于一个区间选它的右端点能覆盖到尽可能多的“未来区间”毕竟这些未来区间的左端点只要不大于这个右端点就会被覆盖到。而选左端点就没有这种优势一个贪心策略要是没有“向后兼容”的能力基本就废了。最大不相交区间数量问题描述是给定N个闭区间选出尽量多的区间使它们两两没有公共点。你猜怎么着解法还是按右端点排序然后从左往右扫能选就选记录上一个选定区间的右端点遇到左端点大于等于它的区间就选它。这两个问题本质上是对偶的最少点数覆盖所有区间等于最多不相交区间数量。证明也很有意思最大不相交区间的数量不可能少于最少点覆盖的点数因为每个点最多只能属于一个被选出的不相交区间也不可能多于否则这些不相交区间就需要至少相同数量的点来覆盖。两个方向一夹就相等了。写代码时有个细节闭区间里“包含端点”会导致判断条件是用还是。如果题目说区间是闭区间点落在端点上也算覆盖那么判断ranges[i].l last即可如果题目说“不能共享端点”那就要写成。这种边界差异在面试里经常被拿来当隐藏坑。2.2 区间分组优先队列维护最右端点区间分组问题给定N个闭区间把它们分成若干组使得每组内部的区间两两不重叠端点可以重叠问最少分几组。做法是按左端点从小到大排序用一个小根堆维护“当前已经开的组里最后一区间的右端点”。遍历每个区间如果当前区间的左端点大于堆顶也就是这个区间可以接到某个组的后面就把堆顶弹出把当前区间的右端点放进堆否则开一个新组直接入堆。最后堆的大小就是答案。sort(ranges, ranges n, [](Range a, Range b){ return a.l b.l; }); priority_queueint, vectorint, greaterint heap; for (int i 0; i n; i) { auto r ranges[i]; if (!heap.empty() heap.top() r.l) heap.pop(); heap.push(r.r); } cout heap.size() endl;为什么按左端点排序因为左端点排序能确保我们在考虑一个新区间时所有可能和它重叠的旧区间都已经处理过了。堆里存的是每组最靠右的端点堆顶就是“最早能空出来”的组的结束时间如果当前区间连最早结束的组都接不进去那它一定得单独开一组。这个排序依据和选点是反的很多人一开始会记混我自己的记忆方法是选点是“向后看”所以看右端点分组是“向前接”所以看左端点。2.3 区间覆盖双指针式的贪心扩展区间覆盖问题给定一个目标区间[s, t]从N个区间里选尽量少的区间把这些区间覆盖住目标区间求最少数量如果不能覆盖则输出-1。做法是把所有区间按左端点排序然后从当前已经覆盖到的位置st开始在“左端点不超过st”的所有区间里选出右端点最大的那个把st更新为这个右端点计数加一。重复这个过程直到st t。每次找右端点最大的区间时不要每次重新遍历而是用一个指针随着st的更新往前走这就是双指针的贪心扫描。sort(ranges, ranges n, [](Range a, Range b){ return a.l b.l; }); int res 0; bool success false; for (int i 0; i n; i) { int j i, maxr -2e9; while (j n ranges[j].l st) { maxr max(maxr, ranges[j].r); j; } if (maxr st) break; // 中间断档覆盖失败 res; if (maxr t) { success true; break; } st maxr; i j - 1; }区间覆盖有一个很容易踩的坑如果当前可选区间里右端点最大的那个都小于st说明从st这个位置开始已经没有任何区间能覆盖到它了这时候直接break输出-1不要心存幻想。另外目标区间如果很大而可用区间之间存在“缝隙”贪心算法扫到缝隙时自然会失败所以判断条件要写成maxr st而不是maxr st因为这取决于区间的开闭定义。3. Huffman树为什么每次合并最小的两堆就是最优3.1 合并果子的贪心直觉与树模型Huffman树问题的经典场景是合并果子有N堆果子每堆有一个重量每次可以把两堆合并成一堆合并的代价是两堆重量之和问把所有果子合并成一堆的最小总代价。很多第一次接触这个题的人会想是不是应该尽量把重的果子留在最后合并答案是反的应该每次挑最轻的两堆先合并。因为一棵合并过程本身就是一棵二叉树叶子节点是原始堆内部节点是合并产生的堆总代价等于所有内部节点权值之和也等于每个叶子节点的权值乘以它到根节点的深度之和。如果你把重果子放在浅层它被重复计算的次数就少把轻果子放在深层它被重复计算得再多也无所谓。所以策略是重量越大的堆在二叉树里的深度应该越小。而“每次挑最小的两个合并”恰好构建出这样一棵带权路径长度最小的树。举个具体例子三堆果子重量分别是1、2、9。如果先合并1和9代价10再合并10和2代价12总代价22。如果先合并1和2代价3再合并3和9代价12总代价15。差别很明显因为9作为重量最大的果子在前一种方案里被计算了两次在后一种方案里只被计算了一次。3.2 证明思路最优二叉树中最小权值节点在最深层严格证明Huffman贪心正确性用的方法是“反证构造”假设最优二叉树T里权重最小的两个叶子节点x和y不在最深层那么我们可以把最深层里的某个叶子节点z和x或y交换。因为x的权重小于等于z交换后整棵树的带权路径长度不会增加所以新树仍然是最优的。反复做这种交换就能构造出一棵“x和y互为兄弟且在最大深度”的最优树。接下来把x和y这两个叶子合并成一个权重为xy的新叶子得到一个规模为n-1的新问题。可以证明原问题的最优解等于新问题的最优解加上xy。于是贪心策略的每一步都不亏所以“每次挑最小的两个合并”是最优的。代码实现直接用优先队列priority_queueint, vectorint, greaterint heap; for (int i 0; i n; i) { int x; cin x; heap.push(x); } int ans 0; while (heap.size() 1) { int a heap.top(); heap.pop(); int b heap.top(); heap.pop(); ans a b; heap.push(a b); } cout ans endl;有一个细节容易忽略如果n 1不需要合并答案应该是0。很多模板代码没处理这个边界但出题人很喜欢塞这种用例。3.3 哈夫曼树的两种变形k叉合并和相邻合并Huffman树在算法题里有两种常见变形。第一种是k叉Huffman树每次可以合并k堆果子问最小代价。这时如果初始堆数不满足(n-1) % (k-1) 0需要补若干个重量为0的虚拟堆让最后一次合并也能凑满k个。这个条件的来源是一次k叉合并会让总堆数减少k-1个从n堆变成1堆总共需要减少n-1次所以必须满足(n-1)是(k-1)的整数倍。如果补完0后依然不整就继续补直到满足为止。第二种变形是“只能合并相邻两堆的石头”问题石子合并这个就不能用Huffman了因为限制“相邻”破坏了贪心的结构需要区间DP复杂度O(n^3)。所以看到合并类题目第一件事就是看有没有“相邻”这个限制条件。没有限制就是Huffman有限制就考虑区间DP这是我做这类题的条件反射。4. 排序不等式调整顺序就是调整全局成本4.1 排队打水问题与“从小到大排”排序不等式的经典场景是排队打水有N个人排队接水第i个人接水需要t_i分钟每个人等待的时间是从开始排队到他接完水为止的总时长问所有人等待时间之和最小是多少。直觉上接水快的人应该排在前面因为排在前面的人被后来者“连累”的次数少。证明也不难假设队伍里有两个相邻的人i和ji在j前面且t_i t_j那么这两个人给总等待时间贡献的部分是在i之前的等待时间不变i这个人的等待时间也不变j的等待时间等于i的等待时间加上t_i如果交换他们的位置j的等待时间会变成原来的等待时间减去t_i再加上t_j比原来小所以交换后总时间一定减小。于是只要存在逆序前面的人时间大于后面的人交换就能优化所以最优排列是时间从小到大。代码很简单排序后累加前缀和sort(t, t n); long long ans 0; for (int i 0; i n; i) { ans t[i] * (n - i - 1); }这里非常容易漏掉用long long因为等待时间最坏情况下是n^2量级。比如n100000每个人时间都是100000总等待时间就是10^10int绝对炸。我自己在竞赛里因为这个原因Wa过不止一次现在看到“最小值/最大值累加”都会条件反射地检查数据类型。4.2 排序不等式的通用形式与识别方法更一般的排序不等式是有两组数a_1 ≤ a_2 ≤ ... ≤ a_nb_1 ≤ b_2 ≤ ... ≤ b_n那么“顺序和”对应位置同序相乘再相加 ≥ “乱序和” ≥ “逆序和”一个升序一个降序相乘再相加。排队打水只是它的一个特例。拿到一道题如果它要求“安排两个序列的对应关系使乘积和最大/最小”或者“安排一批任务的执行顺序使总代价最小”大概率就是排序不等式的变体。比如经典的“任务调度”问题有N个任务每个任务有完成时间和罚款如何排序使总罚款最小这类题的贪心往往也是按某个比值排序本质上是排序不等式的延伸。做题时只要把两个序列拎出来看清楚谁是“从小到大”谁是“从大到小”答案基本就出来了。5. 绝对值不等式中位数为什么永远是对的5.1 货仓选址问题的几何直觉绝对值不等式的经典题是货仓选址数轴上有N家商店坐标分别为x_1, x_2, ..., x_N现在要建一个货仓使货仓到所有商店的距离之和最小问最小距离和是多少。答案是货仓建在所有坐标的中位数上如果N是偶数建在中间两个数之间的任意位置都可以。这个结论很多同学背得很熟但真的理解几何直观的人不多。我的理解方式是这样的把N个点分成最左边和最右边一对货仓到这一对点的距离之和至少是这两个点之间的距离等号当且仅当货仓位于它们之间。再把第二左和第二右配成一对货仓到它们的距离之和也至少是它们之间的距离。每对都这样分析最后如果N是奇数会剩下一个点单独作为中位数货仓直接建在这个点上可以让所有不等式的等号都成立。用公式表示就是| x - x_1 | | x - x_n | |x - x_1| |x_n - x| ≥ |x_n - x_1|这个不等式的意思是货仓到最左和最右两个商店的距离和至少等于这两个商店之间的距离而且货仓只要在它们中间就能取到等号。对所有配对求和总和的最小值就是把每对的商店间距加起来而这个值在x取中位数时可以达到。5.2 一维结论到多维扩展货仓选址只在一维数轴上成立“中位数最优”如果题目改成二维平面上的曼哈顿距离即求min Σ(|x_i - a| |y_i - b|)那就把x和y分开独立处理每一维都取中位数两步合起来就是二维最优解。但如果改成欧几里得距离最优位置就是几何中位数这个没有闭式解通常需要模拟退火之类的方法竞赛里极少考看到也别慌说明出题人没打算让你证明给你样例让你猜结论就行。还有一个我很喜欢的变体最小化到所有点的“切比雪夫距离”即max(|x - x_i|, |y - y_i|)之和。这种题通常先用坐标变换把切比雪夫距离转成曼哈顿距离旋转45度并缩放再套用中位数结论。但这类题识别难度较高需要做过专门的训练才有感觉。我自己遇到这种题的第一反应是先看数据范围和坐标变换特征再做判断。6. 推公式题从“国王游戏”看贪心排序的暴力推导6.1 国王游戏的完整推导过程推公式类题目是贪心里最“玄学”的一类它表面上是排序题但排序依据不是现成的需要自己推。最经典的例子是国王游戏国王和N个大臣站成一排每个人左手和右手各写一个数每个人获得的奖赏是“排在他前面所有人的左手数字乘积”除以“他自己右手数字”然后向下取整。国王固定在第一位要求安排大臣的顺序使获得最多奖赏的大臣的奖赏尽量小求这个最小值。思路是考虑任意两个相邻的大臣i和j。假设这两个大臣之前的所有人大臣左手乘积是Pi的左、右手数字分别是L_i、R_ij的分别是L_j、R_j。如果i排在j前面那么i的奖赏是P / R_ij的奖赏是P * L_i / R_j如果j排在i前面那么j的奖赏是P / R_ji的奖赏是P * L_j / R_i。两个方案里的最大值分别是max(P / R_i, P * L_i / R_j)和max(P / R_j, P * L_j / R_i)都除以P之后比较max(1/R_i, L_i/R_j)和max(1/R_j, L_j/R_i)。一通推导后得到一个简洁的结论按左右手数字的乘积L_i * R_i从小到大排序。这个结论几乎不可能靠直觉猜出来只能老老实实把相邻两个元素的最大值表达式列出来做比较。6.2 大整数陷阱与“耍杂技的牛”国王游戏还有一个非常出名的坑数据范围很大中间结果会超过long long。因为P是前面所有左手数字的乘积可能达到几百位必须写高精度乘法和除法。我在实际做题时先写了个C版本发现溢出又换Python重写才过后来干脆用Java的BigInteger。很多同学第一次做这题都会被坑所以看到“乘积取整”类题目第一反应就要考虑是不是需要高精度。同类题目还有“耍杂技的牛”N头牛叠罗汉每头牛有体重W和力量S每头牛的风险定义为它上面所有牛的体重和减去它自己的力量求最大风险的最小值。推导方式类似结论是按W S从小到大排序。这类题的特征非常明显给你若干个体每个个体有两个属性要求排成一个顺序使某个“最大值最小”或“最小值最大”解法基本都是“交换相邻两项列出比较式化简到只剩两个属性组合的比较”。一旦你能化简出“按A B排序”或者“按A * B排序”题目就结束了剩下的就是排序加扫描。7. 跳跃游戏2和一个实用判断清单7.1 跳跃游戏2的“最远覆盖”贪心热搜词里出现“跳跃游戏2贪心算法”我顺便讲一下这个题。给定一个非负整数数组nums你初始在第一个位置每个位置代表你能跳跃的最大长度目标是到达最后一个位置求最小跳跃次数。保证一定可以到达。贪心策略是维护“当前这一步能到达的最远位置curEnd”和“下一步能到达的最远位置curFarthest”从左往右遍历数组不断更新curFarthest。当遍历到curEnd时说明这一步的覆盖范围已经用尽必须再跳一次于是步数加一curEnd更新为curFarthest。int jump(vectorint nums) { int ans 0, curEnd 0, curFarthest 0; for (int i 0; i nums.size() - 1; i) { curFarthest max(curFarthest, i nums[i]); if (i curEnd) { ans; curEnd curFarthest; } } return ans; }这个代码的边界条件很值得品味循环遍历到倒数第二个位置就停因为最后一个位置不需要再跳出去。很多实现写成遍历到最后一个位置会导致最终步数多算一次。另外注意“最小跳跃次数”和“能否跳到终点”是两个不同的问题前者需要维护两层“最远”后者只需要维护一个“当前能到的最远位置”。7.2 判断一道题能不能贪心的自检清单我把这些年做贪心题总结的经验整理成一个清单题目有没有“最小值/最大值/最少/最多”这类字眼没有的话大概率不是贪心。尝试用“交换相邻两项”能不能推出排序依据能推出就是排序类贪心不能先别急着放弃。决策是不是“眼前最优选完就不用回头”如果选了当前最优后还需要重新调整历史决策说明无后效性不成立基本不是贪心。找一个看似成立的策略去构造反例。构造不出来再尝试证明。时间复杂度如果不是O(n log n)级别想想是不是该用别的算法贪心的复杂度通常都很低如果题目的数据范围要求O(n)或O(n log n)贪心的可能性很大。这套清单不是万能的但能帮我过滤掉至少一半的“伪贪心题”。比如有些题看起来是区间选点实际上要结合差分数组有些题看起来是排序不等式实际上要套二分答案。所以清单只是起点真正靠谱的还是对每个专题的原理有深入理解。做题顺序上我建议先刷区间问题因为它模型化程度最高套路最固定容易建立信心再刷Huffman树和排序不等式这两个几乎就是“背模板”代码量也小接着做绝对值不等式培养把数学式子转化成几何直觉的能力最后啃推公式题因为它最考验推导能力。跳跃游戏这类“覆盖范围”模型可以作为收尾练习因为它把前几种思想的综合应用体现得最明显。贪心这个专题最迷人的地方在于它不像动态规划有明确的状态定义和转移方程也不像图论有固定的算法模板它的每一步都像在走钢丝但真正通了之后你对“怎么证明一个算法是对的”会有完全不一样的理解。希望这篇整理能帮你把这根钢丝走稳。