企业官网建设流程全解析

最近有朋友问我“贪心算法里mex题型的思路”，一开始我觉得这类题目套路比较固定，讲清楚一个例子就能举一反三。但真聊起来才发现，很多人不是不会写贪心循环，而是看不懂“为什么这么贪是对的”——尤其是“最大化mex之和”这种题目，推理链条一旦断了，代码就是背出来的，换一道题立刻蒙。这篇文章我按自己整理这类题目的习惯来写，先讲mex是什么，再拆两类最常见的“最大化mex之和”的原型，然后落代码、讲踩坑，最后顺手把跳跃游戏II的贪心也串进来，因为它们的核心决策逻辑其实是同一套。

1. 先搞懂mex到底是什么，“最大化mex之和”又在做什么

1.1 从生活场景认识mex

mex是“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这M+1个数字，那这一段自己就拥有了所有小于M的数还多一个M，但全局mex是M，说明全局里根本没有M这个数字，矛盾。所以每个子段的mex至多M，k段加起来至多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_{t>=0} g(t)。用上面例子算：g(0)=5（有0的组数）、g(1)=2（有0和1的组数）、g(2)=2（有0、1、2的组数）、g(3)=0，答案就是5+2+2=9。这个拆法我最早看题解时想了很久，后来发现它就是“贡献按层统计”的技巧：把每个组的mex拆成一层一层的“阶梯”，而不是直接看最终高度。理解了这层，分组分配型就成了纯粹的前缀最小值求和问题。

3. 可落地的算法实现与代码拆解

3.1 计数数组预处理与全局mex快速计算

不管走哪条路线，第一步都是统计频率。用C++写的话，直接开一个长度n+1的数组，遍历原数组，值v如果小于等于n就加一。为什么只需要统计到n？因为mex最大不会超过数组长度n——如果一个数组长度是n，最多只能覆盖0到n-1这n个不同的数字，所以mex最多是n。超过n的值对结果没有任何影响，直接忽略就行。

计算全局mex就是扫描cnt数组，从0开始找第一个cnt[i] == 0的位置。这个值的意义在分段型问题里就是“理论上每一段mex的天花板”。代码很简单：

int getMex(const vector<int>& a) { int n = a.size(); vector<int> 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数组要开n+1而不是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 vector<int>& a, int k, int target) { if (target == 0) return true; // 目标为0一定成立 int n = a.size(), need = target, cnt = 0; vector<int> 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且本段第一次出现的v，need就减1。need归零表示这一段已经集齐0到target-1，立刻切段。注意这里没处理“一段内的数字重复出现”的问题——其实不用处理，重复出现的关键数字不影响“是否出现过”的判断，所以只靠vis去重就够了。

为什么这里“立刻切”是安全的？假如当前段已经集齐了所有关键数字，后面再留更多元素进来只会让这段的mex保持target不变（因为关键数字不会少），但会把本该属于后面段的关键数字提前消耗掉。立刻切段是把资源留给后面的段，这是贪心能成立的核心。我之前写过“再多拿几个元素再切”的版本，结果后面段凑不齐，白白判错。

3.3 分组分配问题：从“前缀最小值求和”到线性递推

分组分配型如果我们想做“mex值之和最大”且组数、组容量都有限制，可以围绕上一节的g(t)来求。第一步是统计每个数字v出现的次数cnt[v]，然后从t=0开始逐层推进，维护cur表示当前还能覆盖到第t层的组数。初始cur = 组数m（或者足够大的上限），总答案ans = 0。对于每个t = 0, 1, 2, ...，cur = min(cur, cnt[t])，表示这t这一层最多能有cur个组拿到数字t；随后ans += cur，表示有cur个组的mex值至少是t+1，这cur个1先计入答案。一旦cnt[t] == 0，cur变成0，循环就可以终止，因为后面所有层都没组能覆盖了。

这个递推的实现极其简洁：

int maxMexSum(const vector<int>& a, int groupCount) { int n = a.size(); vector<int> 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..t，mex不小于t+1 } return ans; }

这个代码要注意的是groupCount怎么来。如果题目说“最多分成m组”，那你实际上不会真的用满m组去分——组数越多，每个数字就越分散，答案通常越大，所以直接取m就行。如果题目说“每组容量上限是c，元素必须全部分完，求最大mex之和”，这时候组数需要从元素总数推：最坏情况下每个组至少要有1个元素，所以组数不能超过n（n是元素数）；但另一种策略是让某些组根本不放任何元素，它们mex为0，不贡献答案，所以真正有意义的组其实就是尽量多开，但每组的容量c又限制了“每个组内最多同时放几个关键数字”。比如c=2，却硬要让一个组同时拥有0、1、2三个数字，那是不可能的。所以容量c会给每层可覆盖的组数加上额外限制：t+1层要求每组的“有效占用”至少t+1个位置。处理方式是在循环里额外判断，如果t+1 > c，那么cur要降为0，因为没有任何一组能装下0到t这么多个关键数字。

说实话，分组分配型题目在实际面试里变体非常多，我上面给的是最核心的“无容量限制”版本。遇到带容量参数c的题目，建议你先按无容量算一版，再单独检查mex是否会超过c，超出的部分直接截断成c。比如一组最多装3个数字，那mex最大就是3，和容量一致时答案就是前面若干层贡献之和。这个“按层求和再截断”的做法，在几乎所有变体里都能保底。

4. 常见错误与排查技巧

4.1 错误一：段内独立性误判导致结果偏大

分段型问题里最经典的错误是“每段各算各的mex，然后把它们加起来”。听起来没毛病，但实际样例一测就错。比如数组[0, 1, 2, 0, 1, 2]，k=2。如果每段单独算mex，第一段[0, 1, 2]的mex是3，第二段[0, 1, 2]的mex是3，和是6，看起来完美。但换成数组[0, 0, 1, 1, 2, 2]，同样是k=2，如果每段单独算，你可以切[0, 0, 1]和[1, 2, 2]，各自的mex是2和0，和是2；但最优切法其实是[0, 0, 1, 1]和[2, 2]，第一段mex是2，第二段mex是0，和仍然是2。而如果天真地认为“每段都要拿全局mex=3”，判定能切成两段且每段mex都大于2，实际上不行——因为3这个数字全局都不存在，任何段都不可能mex达到3。所以凡是算出来答案比k * M还大的代码，第一步就要检查：你是不是把mex想成了“本段最大数字+1”，而不是“本段最小的未出现整数”。

4.2 错误二：把单个值出现次数和可覆盖组数搞混

分组分配型里有个特别隐蔽的坑。假设cnt[0] = 5，cnt[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之和能到100+100+100=300。但题目说每组容量c=1，那就完了：一组只能装一个数字，装了0就装不了1，所以mex之和最多是100（每组的mex最多1）。容量c=2时，每组最多同时拥有0和1，mex最多2。这个上界是容量硬约束，不是频率能突破的。遇到这类题，我的排查顺序是先算容量上界cap = min(元素总数/组数, c)，再往下压。举个实际例子：n=10, m=5, c=2，元素包含0到5各2次，看起来可以做到每组的mex都是2？不一定，关键看0到1是否每个数字都出现了至少5次。发现0只出现2次，1只出现2次，那最多2组mex=2，其他组mex最多1，答案就是22 + 31 = 7。容量约束在这里的真实作用是截断“每组mex”的上限，而不是改变频率统计的逐层计算方式。

4.4 常见问题速查表

我在实际写这类题时，还会额外打一个“假组数”的补丁：如果题目允许某些组为空，那么空组的mex是0，不会贡献答案。但由于空组不贡献，我习惯直接把有意义的组数预先设为“元素个数除以1”或者题目给的m，然后统一跑递推，不用特殊处理空组。省心。

5. 从mex贪心延伸到跳跃游戏II：贪心题型的通用识别法则

5.1 跳跃游戏II的贪心思维回顾

“跳跃游戏II”是另一个高频贪心题：给你一个数组nums，nums[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分组里，让一个组从mex=2升到mex=3，需要消耗数字2的一个实例，而这个消耗不会影响其他组拥有数字0和1，所以不会破坏其他组的楼梯。但如果题目把资源改成“每组最多c个元素”，让一个组升到mex=c+1就会因为容量不够而失败，此时楼梯图被容量上界砍了一刀——这也不是不能贪心，只是上限变了。真正会破坏贪心的是那种“资源互斥”的变体，比如每个数字只能使用一次且每个组必须连续取原数组的一段，那种就得回到区间DP了。

最后再分享一个小技巧：不管题目怎么变形，先写出“无限制情况下”的贪心答案，再用限制条件去截断，通常比一上来就写完整版要快。我在调试带容量c的分组题时，就是先跑一遍无容量版本拿到一个答案，再手动检查“有没有哪一层的g(t)超过容量x(t+1)”，有就截断，几轮就能调对。这比一上来就考虑所有约束要直观得多，也更容易定位是逻辑错了还是边界条件漏了。