最近有朋友问我“贪心算法里mex题型的思路”一开始我觉得这类题目套路比较固定讲清楚一个例子就能举一反三。但真聊起来才发现很多人不是不会写贪心循环而是看不懂“为什么这么贪是对的”——尤其是“最大化mex之和”这种题目推理链条一旦断了代码就是背出来的换一道题立刻蒙。这篇文章我按自己整理这类题目的习惯来写先讲mex是什么再拆两类最常见的“最大化mex之和”的原型然后落代码、讲踩坑最后顺手把跳跃游戏II的贪心也串进来因为它们的核心决策逻辑其实是同一套。1. 先搞懂mex到底是什么“最大化mex之和”又在做什么1.1 从生活场景认识mexmex是“Minimum EXcluded value”的缩写意思是“最小的未出现的非负整数”。这个概念听起来绕用生活场景一对比就清楚了。你收集盲盒手办一套系列一般是0号到9号共10个隐藏编号但你柜子里已经有0、1、2、4、5号缺3号。那么你当前收藏集合的mex就是3——因为3是第一个没收集到的编号。如果你收藏更夸张0到9全都有了那mex就是10。所以mex回答的是这样一个问题从0开始数数到哪个数字的时候你第一次没有这个数字就是mex。把场景抽象回数组给一个数组[1, 0, 2, 4, 0, 0]问这个集合的mex是多少从0开始看0有1有2有3没有所以答案是3。注意这里“4出现没出现”已经无所谓了因为mex只关心从0开始连续覆盖到哪一位。这个“只关注连续前缀覆盖”的特性是后面所有贪心策略成立的地基。1.2 问题原型拆解两类常见出题姿势“最大化mex之和”这个说法其实覆盖了好几种不同的题。第一种是“分段型”给你一个数组和一个整数k要求把数组切成k个非空连续子段每一段分别算mex然后求和目标是让这个和最大。第二种是“分组分配型”给你一个数组和一个组容量c每个组最多装c个元素要求把所有元素分到若干个组里每组mex之和要最大化组数可以自由决定也可能限定为某个固定值m。第三种是“子集型”从数组里选出若干个集合每个集合的mex之和最大通常配有限制条件。这三种模型里前两种在竞赛和面试里出现频率最高。很多人会把它们当成完全不同的题去记但我的经验是它们底层共用同一个贪心逻辑——“从0开始一层一层往上铺铺不动就结算”。把这个逻辑吃透三种题的代码都只是微调。先记住这句话下面两节我会证明它为什么对。2. 贪心策略的核心原理为什么“逐层填充”是对的2.1 关键观察段与段之间可以任意重组先看分段型问题。很多人的第一反应是“每一段的划分会影响每一段的mex那贪心怎么保证不拆错”确实段的边界会影响单个段内的mex但题目问的是所有段mex之和最大这里藏着一个反直觉的结论当k确定时只要整个数组的mex记为M那么最大答案就是k * M而且这个上限一定能达到。证明思路不复杂。先说为什么不可能超过k * M任何一段的mex都不会大于全局mex M因为如果有一段包含0到M这M1个数字那这一段自己就拥有了所有小于M的数还多一个M但全局mex是M说明全局里根本没有M这个数字矛盾。所以每个子段的mex至多Mk段加起来至多kM。再说为什么可以达到我不需要关心段长是否均匀只需要构造性地把0、1、2、…、M-1这M个数字分别放进不同的段里每段放一个剩下的所有数字随便拼到任意一段后面。这样一来每个段都拿到了一个关键数字它的mex至少是1但这还只是把和做到k远没到kM。要做满kM需要每个段都拥有0到M-1中的全部M个数字这就要把0到M-1的数字各复制k份——问题来了全局mex是M只说明M没出现过但0到M-1每个数字可不一定都出现了k次。所以“每段mex都能到M”的构造并不总是成立它依赖于数字的频率。看到这里你会发现分段问题真正要验证的其实是“能不能把数组切成k段使得每一段都包含0到M-1的全部M个数字”。一旦能答案就是kM不能就往回收。这个“往回收”的过程就是贪心发挥作用的地方。2.2 先解决“能否分成k段”的约束判断怎么判断能否分成k段且每段都包含0到M-1所有数朴素做法是从左往右扫每凑齐一个“完整前缀集合”就切一刀。具体说一下维护一个计数器need初始为M表示当前这段还需要多少个关键数字。维护一个计数数组记录当前段内每个关键数字出现了几次。从左到右遍历数组遇到一个值v如果v M且这个值在本段第一次出现就把need减1。当need变成0时说明当前这一段已经集齐了0到M-1立刻在这里切一刀然后重新开始下一段。遍历完统计切出来的完整段数如果大于等于k就说明可以拼出k段完整集合剩余不完整的部分全部丢给某一段当“边角料”不影响那段mex。这个算法的复杂度是O(n * M)因为每个元素都可能触发对M个数字的去重判断遇到大M会超时。优化办法是记录一个vis数组和一个visStamp时间戳用时间戳代替每次清空数组这样每个元素处理都是O(1)整体O(n)。我写这类二分验证时都会用时间戳优化去重后面给出的模板就是这样。还有一个更隐蔽的剪枝如果k n / M说明即使把关键数字平均分配也不可能每段都凑齐M个直接判false可以省掉一次完整扫描。2.3 数字出现次数的“木桶效应”与冗余元素现在换到分组分配型它的贪心逻辑更直观。假设你手头有c个组每组容量无限或者足够大现在要把数组元素分配进去最大化每组mex之和。由于mex只关心“从0开始的连续整数是否齐全”这个问题的答案完全由每个数字的出现次数决定和具体是哪些元素重复无关。举个例子数组里0出现了5次1出现了2次2出现了3次3出现了0次。那么最多能有几组的mex大于0取决于0的组数5组。最多能有几组的mex大于1需要同时拥有0和1取两者次数最小值min(5, 2)2组。最多能有几组的mex大于2需要同时拥有0、1、2取三者最小值min(5, 2, 3)2组。mex大于3因为3压根没出现所以0组。于是各层能覆盖的组数分别是大于0有5组、大于1有2组、大于2有2组、大于3有0组把这些加起来就是总答案9不对这里要小心mex之和并不是把“大于某值”的组数直接相加。这里我需要把公式讲清楚。设g(t)表示“mex值大于t的组的数量”也就是能同时包含0、1、…、t这些数字的组的数量。那么一个组的mex如果是x它对答案的贡献是x。而x这个值可以拆成x 1 1 … 1共x个1等价于它对g(0)、g(1)、…、g(x-1)各贡献了1。反过来对所有组的mex求和就等于sum_{t0} g(t)。用上面例子算g(0)5有0的组数、g(1)2有0和1的组数、g(2)2有0、1、2的组数、g(3)0答案就是5229。这个拆法我最早看题解时想了很久后来发现它就是“贡献按层统计”的技巧把每个组的mex拆成一层一层的“阶梯”而不是直接看最终高度。理解了这层分组分配型就成了纯粹的前缀最小值求和问题。3. 可落地的算法实现与代码拆解3.1 计数数组预处理与全局mex快速计算不管走哪条路线第一步都是统计频率。用C写的话直接开一个长度n1的数组遍历原数组值v如果小于等于n就加一。为什么只需要统计到n因为mex最大不会超过数组长度n——如果一个数组长度是n最多只能覆盖0到n-1这n个不同的数字所以mex最多是n。超过n的值对结果没有任何影响直接忽略就行。计算全局mex就是扫描cnt数组从0开始找第一个cnt[i] 0的位置。这个值的意义在分段型问题里就是“理论上每一段mex的天花板”。代码很简单int getMex(const vectorint a) { int n a.size(); vectorint cnt(n 1, 0); for (int v : a) { if (v n) cnt[v]; } for (int i 0; i n; i) { if (cnt[i] 0) return i; } return n 1; // 不会走到 }这里有个容易忽略的点cnt数组要开n1而不是n。因为如果数组里恰好包含0到n-1的所有数字mex是n此时需要访问cnt[n]而n这个下标的初始值正好是0保证循环能停在对的位置。我见过不少人在边界上翻车比如数组全0长度5开cnt[5]的话访问cnt[0]、cnt[1]…cnt[5]下标5是越界的直接RE。3.2 分段问题对目标值做二分验证分段型问题的标准解法是二分答案。最外层的思路是先求出全局mex M然后准备验证“能否切出k段使每段mex都至少为X”。如果X M那直接false因为全局都没有M这个数字任何一段的mex也不可能超过M。一旦验证能切出至少k段答案就更新为min(全局mex, X) * k里的最大值。更常见的简化写法是从M开始往下试第一个能成功切出k段的t答案就是t * k。因为答案具备单调性如果能切出每段mex t的k段那么t变小之后必然还能切出来。所以可以直接二分t。验证函数写出来大概是bool canSplit(const vectorint a, int k, int target) { if (target 0) return true; // 目标为0一定成立 int n a.size(), need target, cnt 0; vectorint vis(target, 0); int stamp 0; for (int v : a) { if (v target) { if (vis[v] ! stamp) { vis[v] stamp; need--; } } if (need 0) { cnt; if (cnt k) return true; stamp; need target; } } return false; }解释几个细节。vis数组配合stamp时间戳相当于每开一个新段就“假装清空”一次访问标记但实际没有重置数组省下了O(target)的初始化成本。need表示当前段还差几个关键数字遇到一个v target且本段第一次出现的vneed就减1。need归零表示这一段已经集齐0到target-1立刻切段。注意这里没处理“一段内的数字重复出现”的问题——其实不用处理重复出现的关键数字不影响“是否出现过”的判断所以只靠vis去重就够了。为什么这里“立刻切”是安全的假如当前段已经集齐了所有关键数字后面再留更多元素进来只会让这段的mex保持target不变因为关键数字不会少但会把本该属于后面段的关键数字提前消耗掉。立刻切段是把资源留给后面的段这是贪心能成立的核心。我之前写过“再多拿几个元素再切”的版本结果后面段凑不齐白白判错。3.3 分组分配问题从“前缀最小值求和”到线性递推分组分配型如果我们想做“mex值之和最大”且组数、组容量都有限制可以围绕上一节的g(t)来求。第一步是统计每个数字v出现的次数cnt[v]然后从t0开始逐层推进维护cur表示当前还能覆盖到第t层的组数。初始cur 组数m或者足够大的上限总答案ans 0。对于每个t 0, 1, 2, ...cur min(cur, cnt[t])表示这t这一层最多能有cur个组拿到数字t随后ans cur表示有cur个组的mex值至少是t1这cur个1先计入答案。一旦cnt[t] 0cur变成0循环就可以终止因为后面所有层都没组能覆盖了。这个递推的实现极其简洁int maxMexSum(const vectorint a, int groupCount) { int n a.size(); vectorint cnt(n 1, 0); for (int v : a) { if (v n) cnt[v]; } int cur groupCount, ans 0; for (int t 0; t n; t) { cur min(cur, cnt[t]); if (cur 0) break; ans cur; // 这cur个组都至少拥有0..tmex不小于t1 } return ans; }这个代码要注意的是groupCount怎么来。如果题目说“最多分成m组”那你实际上不会真的用满m组去分——组数越多每个数字就越分散答案通常越大所以直接取m就行。如果题目说“每组容量上限是c元素必须全部分完求最大mex之和”这时候组数需要从元素总数推最坏情况下每个组至少要有1个元素所以组数不能超过nn是元素数但另一种策略是让某些组根本不放任何元素它们mex为0不贡献答案所以真正有意义的组其实就是尽量多开但每组的容量c又限制了“每个组内最多同时放几个关键数字”。比如c2却硬要让一个组同时拥有0、1、2三个数字那是不可能的。所以容量c会给每层可覆盖的组数加上额外限制t1层要求每组的“有效占用”至少t1个位置。处理方式是在循环里额外判断如果t1 c那么cur要降为0因为没有任何一组能装下0到t这么多个关键数字。说实话分组分配型题目在实际面试里变体非常多我上面给的是最核心的“无容量限制”版本。遇到带容量参数c的题目建议你先按无容量算一版再单独检查mex是否会超过c超出的部分直接截断成c。比如一组最多装3个数字那mex最大就是3和容量一致时答案就是前面若干层贡献之和。这个“按层求和再截断”的做法在几乎所有变体里都能保底。4. 常见错误与排查技巧4.1 错误一段内独立性误判导致结果偏大分段型问题里最经典的错误是“每段各算各的mex然后把它们加起来”。听起来没毛病但实际样例一测就错。比如数组[0, 1, 2, 0, 1, 2]k2。如果每段单独算mex第一段[0, 1, 2]的mex是3第二段[0, 1, 2]的mex是3和是6看起来完美。但换成数组[0, 0, 1, 1, 2, 2]同样是k2如果每段单独算你可以切[0, 0, 1]和[1, 2, 2]各自的mex是2和0和是2但最优切法其实是[0, 0, 1, 1]和[2, 2]第一段mex是2第二段mex是0和仍然是2。而如果天真地认为“每段都要拿全局mex3”判定能切成两段且每段mex都大于2实际上不行——因为3这个数字全局都不存在任何段都不可能mex达到3。所以凡是算出来答案比k * M还大的代码第一步就要检查你是不是把mex想成了“本段最大数字1”而不是“本段最小的未出现整数”。4.2 错误二把单个值出现次数和可覆盖组数搞混分组分配型里有个特别隐蔽的坑。假设cnt[0] 5cnt[1] 2有人会说“mex大于1的组最多2组因为1只出现了2次”这个对。但接下来问“mex大于2的组最多几组”有人会答“min(cnt[0], cnt[1], cnt[2]) min(5, 2, 3) 2”这里就有点问题了——min函数算出来的确实是2但你要意识到这2组并不是“同一组在承担0和1和2”而是你要从5个拥有0的组里挑出2个组再去分配仅有的2个1最后再从这2个组里配上3个2。如果这些数字都是“可自由分配”的那当然没问题如果题目规定“原数组里每个位置的元素必须原样放进某个组不能复制”那你必须从原数组里按出现位置分配。幸运的是mex只关心集合里有没有这个数字不关心位置所以自由分配是成立的。但如果你在实现时维护了一个二维矩阵“第i组有哪些数字”而不是直接用计数数组算前缀最小值就会引入大量没必要的分配冲突然后debug到怀疑人生。我的建议是分组分配型一律用频率统计别手写分配方案。4.3 错误三忽略容量参数对mex上界的影响再谈带容量的分组题。有时候你算出来的g(t)非常大比如0出现100次1出现100次组数上限100看起来mex之和能到100100100300。但题目说每组容量c1那就完了一组只能装一个数字装了0就装不了1所以mex之和最多是100每组的mex最多1。容量c2时每组最多同时拥有0和1mex最多2。这个上界是容量硬约束不是频率能突破的。遇到这类题我的排查顺序是先算容量上界cap min(元素总数/组数, c)再往下压。举个实际例子n10, m5, c2元素包含0到5各2次看起来可以做到每组的mex都是2不一定关键看0到1是否每个数字都出现了至少5次。发现0只出现2次1只出现2次那最多2组mex2其他组mex最多1答案就是22 31 7。容量约束在这里的真实作用是截断“每组mex”的上限而不是改变频率统计的逐层计算方式。4.4 常见问题速查表症状可能原因排查方法分段型答案超过k * 全局mex误把全局mex上限当成无限验证“是否存在段内mex 全局mex”的情况若全局缺某个数则任何段都不可能包含它分段型验证函数超时vis数组每段都重置改用stamp时间戳每段只改stamp值不真正清空数组分组型答案偏小容量c限制没考虑检查每组能塞的关键数字最大值cmex不可能超过c分组型答案偏大把cnt[t]直接当成“第t层的组数”累加必须逐层取前缀最小值cur min(cur, cnt[t])再累加cur边界REcnt数组开小了数组长度n的mex可能到nvector开n1并检查v n再统计我在实际写这类题时还会额外打一个“假组数”的补丁如果题目允许某些组为空那么空组的mex是0不会贡献答案。但由于空组不贡献我习惯直接把有意义的组数预先设为“元素个数除以1”或者题目给的m然后统一跑递推不用特殊处理空组。省心。5. 从mex贪心延伸到跳跃游戏II贪心题型的通用识别法则5.1 跳跃游戏II的贪心思维回顾“跳跃游戏II”是另一个高频贪心题给你一个数组numsnums[i]表示你在下标i处最多能往前跳多少步要求从下标0跳到最后一个位置最少跳几次。很多人第一次接触时容易想到动态规划但状态转移是O(n^2)而贪心解法只需O(n)。标准写法是维护两个变量当前步能到达的最远位置curEnd、下一步能到达的最远位置nextEnd。遍历每个位置i不断更新nextEnd max(nextEnd, i nums[i])当i走到curEnd时说明当前这一跳已经到极限了必须跳一次把curEnd更新成nextEnd步数加1。这个写法的关键观察是在当前这一跳覆盖的区间里我只需要记录“下一步最远能到哪”而不需要纠结具体跳到哪个点。因为不管中间选哪个点跳最终能覆盖的范围是这些点所有可达位置的并集并集的最远边界就是下一步的最远位置。这个“维护当前覆盖区间内的最远扩展”思想和mex题里的“逐层维护当前能覆盖的组数”非常像——一个是维护位置范围一个是维护值域层级但决策逻辑都是“能扩展就扩展扩展不动就结算”。5.2 mex题目与跳跃问题的共性局部最优如何不亏全局我把两类题放在一起是因为它们都符合一个通用模式状态可以被表示成“当前已经覆盖到什么程度”且每次扩展只会让覆盖程度单调增加不存在“先缩回去再扩展更好”的情况。在跳跃游戏里你跳的次数越多cover肯定越大不会出现“少跳一步但后面反而跳得更远”的反例因为下一跳的可达范围只取决于当前位置而当前位置一旦往前走覆盖范围只会更大。在mex分组里你让更多组拿到数字0不会影响后面数字1的分配因为每个数字是独立的资源先分配0并不会让1“变少”——如果先分配1再分配0唯一变化是某些组先缺0导致最终mex更小所以先处理小数字是严格不劣的。这就是“无后效性的贪心”的典型判定标准局部最优选择不影响后续可选集合。我在判断一道题能不能贪心时会抽象出一个“覆盖量”变量然后问自己三个问题第一每一步的操作能不能让覆盖量单调不减第二有没有可能某一步为了覆盖量更大先把当前覆盖量退回去第三覆盖量的上限是否由全局频率或范围边界唯一确定如果三个答案分别是“能、不可能、是”那这道题大概率能贪心。跳跃游戏II满足mex分段满足mex分组也满足。反过来如果发现某一步会消耗共享资源且分配顺序会改变后续可用量比如背包问题那就不是贪心能解决的老老实实动态规划。5.3 判断一道题能不能用贪心的小技巧除了上面的抽象判断我还有个更实操的小技巧画“楼梯图”。把每个组的mex画成一级一级的楼梯楼梯的高度就是mex值。然后问自己如果我让某一层的楼梯多了一级会不会导致另一层楼梯少了一级在mex分组里让一个组从mex2升到mex3需要消耗数字2的一个实例而这个消耗不会影响其他组拥有数字0和1所以不会破坏其他组的楼梯。但如果题目把资源改成“每组最多c个元素”让一个组升到mexc1就会因为容量不够而失败此时楼梯图被容量上界砍了一刀——这也不是不能贪心只是上限变了。真正会破坏贪心的是那种“资源互斥”的变体比如每个数字只能使用一次且每个组必须连续取原数组的一段那种就得回到区间DP了。最后再分享一个小技巧不管题目怎么变形先写出“无限制情况下”的贪心答案再用限制条件去截断通常比一上来就写完整版要快。我在调试带容量c的分组题时就是先跑一遍无容量版本拿到一个答案再手动检查“有没有哪一层的g(t)超过容量x(t1)”有就截断几轮就能调对。这比一上来就考虑所有约束要直观得多也更容易定位是逻辑错了还是边界条件漏了。