MEX (最小未出现值) 理论与实践¶

MEX（Minimum EXcluded value / 最小未出现的非负整数） 是算法竞赛与离散数学中极具特色的一类算子。它不仅是公平组合博弈（Sprague-Grundy 定理）的基石，更广泛应用于原地哈希（In-Place Hash）、动态集合维护、区间离线扫描线、树上子树查询以及同余贪心构造等多种核心算法模型中。

1. MEX 的数学定义与基本性质¶

1.1 基础定义¶

对于一个包含非负整数的集合或多重集 \(S \subseteq \mathbb{N}_{\ge 0}\)，其 \(\text{mex}(S)\) 定义为不属于集合 \(S\) 的最小非负整数：

\[ \text{mex}(S) = \min \{ x \in \mathbb{N}_{\ge 0} \mid x \notin S \} \]

示例：
\(\text{mex}(\{1, 2, 3\}) = 0\)（因为 \(0\) 不在集合中）；
\(\text{mex}(\{0, 1, 2, 4, 5\}) = 3\)；
\(\text{mex}(\emptyset) = 0\)；
\(\text{mex}(\{0, 1, 2, \dots, k-1\}) = k\)。

在某些具体应用场景中（如 LeetCode 41），问题可能定义在正整数集 \(\mathbb{N}_{> 0} = \{1, 2, 3, \dots\}\) 上，称为 \(1\)-indexed MEX，其性质与非负整数版本完全对偶。

1.2 核心性质与抽屉原理 (Pigeonhole Principle)¶

定理（MEX 的有界性）：对于任意大小为 \(N\) 的集合或数组 \(S\)（无论其中包含何种范围的整数、负数或重复元素），其非负整数 MEX 必定满足：

\[ 0 \le \text{mex}(S) \le N \]

若定义在正整数集（\(1\)-indexed MEX），则必定满足：

\[ 1 \le \text{mex}_{1}(S) \le N + 1 \]

证明：假设 \(\text{mex}(S) > N\)。根据 MEX 的定义，这意味着 \(0, 1, 2, \dots, N\) 这 \(N+1\) 个互不相同的非负整数都必须属于集合 \(S\)。然而集合 \(S\) 最多只能容纳 \(N\) 个不同的元素，由抽屉原理（Pigeonhole Principle）产生矛盾。因此 \(\text{mex}(S)\) 绝不可能超过 \(N\)。

算法推论：

在求任意长度为 \(N\) 的数组的 MEX 时，所有负数、大于 \(N\) 的数以及重复出现的数字，均对最终的 MEX 结果没有任何直接贡献；
我们只需关注落入有效取值范围 \([0, N-1]\)（或 \([1, N]\)）之内的元素；
这一定理直接奠定了原地哈希（\(\mathcal{O}(N)\) 时间、\(\mathcal{O}(1)\) 空间）的理论基础。

2. 静态数组 MEX 与原地哈希 (In-Place Hashing)¶

当给定一个静态数组，要求以 \(\mathcal{O}(N)\) 时间和严格 \(\mathcal{O}(1)\) 额外空间求解其 MEX 时，最强有力的工具就是原地哈希（又称置换归位法 / Cyclic Placement）。

2.1 算法思路¶

利用数组本身充当哈希表：

目标：将每个落在有效范围内的数值 \(x\)，交换放置到它对应的下标位置上（例如 \(x \in [0, N-1]\) 放到下标 \(x\) 处；或 \(x \in [1, N]\) 放到下标 \(x-1\) 处）。
遍历数组中的每一个位置 \(i\)：
如果当前位置的值 \(nums[i]\) 落在合法范围内，且它尚未处于自己应在的位置（即 \(nums[nums[i]] \ne nums[i]\)），就通过 while 循环将其与目标位置的元素持续进行 swap；
直到当前位置换入了一个非法值、或者换入了一个已经在对应位置有副本的重复值时，停止交换，指针推进。
最后顺序扫描一次数组，第一个满足 \(nums[i] \ne i\) 的下标就是答案；若全部对齐，则答案为 \(N\)。

2.2 复杂度证明¶

虽然代码中包含 while 循环嵌套，但每一次有效的 swap 操作，都会将至少一个元素永久放置到其正确的终态索引上。一旦某个元素被正确归位，后续的扫描和交换绝不会再将其移走。因此，对于长度为 \(N\) 的数组，全局发生的 swap 总次数严格不会超过 \(N\) 次。总时间复杂度严格为线性 \(\mathcal{O}(N)\)，额外空间复杂度严格为 \(\mathcal{O}(1)\)。

2.3 C++ 模板 (支持 0-indexed 与 1-indexed)¶

#include <vector>
#include <algorithm>

// 求解非负整数 MEX (0-indexed: 目标范围 [0, n])
// 时间复杂度: O(N), 空间复杂度: O(1) (修改原数组)
int get_mex_0_indexed(std::vector<int> &nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        // 当 nums[i] 落在 [0, n-1] 且未就位时持续置换
        while (nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i]) {
            std::swap(nums[i], nums[nums[i]]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i) return i;
    }
    return n;
}

// 求解正整数 MEX (1-indexed: 目标范围 [1, n+1]，如 LeetCode 41)
// 时间复杂度: O(N), 空间复杂度: O(1)
int get_mex_1_indexed(std::vector<int> &nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        // 数值 x 应当放置在下标 x - 1
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            std::swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

2.4 深度精析与真题实战：LeetCode 41 (缺失的第一个正数)¶

LeetCode 41 - 缺失的第一个正数 (First Missing Positive) 是原地哈希和 MEX 领域最经典、也是最著名的“教科书级”标杆题目。

1. 题目重述与严苛约束¶

输入：一个未排序的整数数组 nums；
输出：找出其中没有出现的最小的正整数（\(1\)-indexed MEX）；
限制：算法的时间复杂度必须是 \(\mathcal{O}(N)\)，并且只能使用 \(\mathcal{O}(1)\) 的常数额外空间。

2. 算法 Intuition（直觉思维跃迁）¶

面对本题，如何从零推导出最优解法？关键在于一个核心矛盾与三次思维跃迁：

矛盾倒逼思考：无法申请新内存的“哈希表需求”
常规思路是用一个哈希表或布尔数组 visited 登记所有出现过的正数，然后按 \(1, 2, 3, \dots\) 顺序查漏，耗时 \(\mathcal{O}(N)\) 但需要 \(\mathcal{O}(N)\) 额外内存；
题目卡死必须 \(\mathcal{O}(1)\) 空间。这启发我们：整个程序里唯一拥有 \(N\) 个存储单元的地方，就是输入数组 nums 本身！必须直接把原数组就地当做哈希表使用。
抽屉原理锁定解空间：有效信息的极致压缩
数组长度为 \(N\)，其中可能包含 \(-100\)、上百亿的极大数或海量重复数字；
依据抽屉原理：若数组刚好包含 \(1 \sim N\)，则缺失正整数为 \(N + 1\)；若缺少任何一个数，缺失的数必定属于 \([1, N]\)；
结论：答案必然且唯一定落在 \([1, N + 1]\) 内！所有 \(\le 0\) 的数、超过 \(N\) 的大数均为“杂质”，无需为其安排位置，我们只需关心 \(1 \sim N\) 是否到场。
“对号入座”的教室考勤隐喻
我们可以把数组看作一间有 \(N\) 张桌子（下标 \(0 \sim N-1\)）的教室，桌位应严格对应学生工号 \(1 \sim N\)（数值 \(x\) 应当坐在下标 \(x - 1\) 上）；
遍历每个座位：如果发现上面坐的不是对应号码的学生，就把他交换送到他该去的正确桌位上，并将那张桌子上的人拉回来继续识别；如果换回来的是负数或大数（外校闲杂人员），则暂时留他在当前桌位占位；
最终验收：巡视全场，第一个名不副实的桌号（如 2 号桌上坐着外校人员），立刻判定 2 号学生缺席！

3. 关键避坑细节：为什么不能写 `nums[i] != i + 1`？¶

[!CAUTION] 在 while 条件中，必须写成 nums[nums[i] - 1] != nums[i]，而严禁写成： while (nums[i] >= 1 && nums[i] <= n && nums[i] != i + 1)

致命反例分析：设输入为 nums = [1, 1]（\(n = 2\)）：
当外层遍历到 \(i = 1\) 时，当前数值为 \(nums[1] = 1\)；
若只判断 \(nums[1] \ne 1 + 1\)（\(1 \ne 2\)），条件成立，程序将执行 swap(nums[1], nums[0])；
但下标 \(0\) 处本来就已经是 \(1\) 了，交换后数组毫无变化，\(nums[1]\) 仍然为 \(1\)，导致 while 条件永远为真，程序陷入死循环（TLE）！
正确逻辑： nums[nums[i] - 1] != nums[i] 的含义是：“目标槽位是否已经存在正确的副本了”。如果目标槽位已经正确归位，当前多余的重复值直接停止交换，安全推进。

4. 严格势能复杂度证明：为什么不是 \(\mathcal{O}(N^2)\)？¶

代码结构虽然是 for 循环嵌套 while 循环，但我们可以通过已归位元素的单调性进行势能分析：

每次发生有效的 std::swap，必定会把至少一个数值送回它最终的合法座位（即下标 \(nums[i] - 1\)）；
元素一旦回到自己的正确位置，根据 nums[nums[i] - 1] != nums[i] 条件，后续它绝对不会再被换走；
整个数组总共只有 \(N\) 个位置，因此全生命周期内成功的 swap 总次数严格 \(\le N\)；
外部循环推进 \(N\) 次，内部总交换至多 \(N\) 次，因此总时间步数严格小于 \(2N\)，时间复杂度严格为 \(\mathcal{O}(N)\)；空间复杂度严格为 \(\mathcal{O}(1)\)。

5. 完整代码实现 (AC 模板)¶

C++Python

#include <vector>
#include <algorithm>

class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        int n = nums.size();

        // 1. 原地置换归位：将数值 x 放置在下标 x - 1 上
        for (int i = 0; i < n; ++i) {
            // 条件：属于合法正整数区间 [1, n]，且目标槽位尚未归位
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                std::swap(nums[i], nums[nums[i] - 1]);
            }
        }

        // 2. 顺序查漏：寻找首个名不副实的位置
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 3. 1 ~ n 全部就位，缺失的必为 n + 1
        return n + 1;
    }
};

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)

        # 原地置换归位
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                target = nums[i] - 1
                nums[i], nums[target] = nums[target], nums[i]

        # 顺序查漏
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

6. 实例状态演进模拟表 (Dry Run)¶

以 nums = [3, 4, -1, 1] 为例（\(n = 4\)）：

步骤	循环指针 \(i\)	当前操作与原因说明	数组状态 `nums`
初始	-	初始乱序输入	`[3, 4, -1, 1]`
1	\(i = 0\)	\(nums[0] = 3 \in [1, 4]\)，与目标槽位 \(nums[2] = -1\) 交换	`[-1, 4, 3, 1]`
2	\(i = 0\)	新换入的 \(nums[0] = -1 \notin [1, 4]\)，停止交换，推进 \(i\)	`[-1, 4, 3, 1]`
3	\(i = 1\)	\(nums[1] = 4 \in [1, 4]\)，与目标槽位 \(nums[3] = 1\) 交换	`[-1, 1, 3, 4]`
4	\(i = 1\)	新换入的 \(nums[1] = 1 \in [1, 4]\)，与目标槽位 \(nums[0] = -1\) 交换	`[1, -1, 3, 4]`
5	\(i = 1\)	新换入的 \(nums[1] = -1 \notin [1, 4]\)，停止交换，推进 \(i\)	`[1, -1, 3, 4]`
6	\(i = 2\)	\(nums[2] = 3\) 已在其正确位置 \(2\)，跳过	`[1, -1, 3, 4]`
7	\(i = 3\)	\(nums[3] = 4\) 已在其正确位置 \(3\)，跳过	`[1, -1, 3, 4]`
8	查漏 \(i=0\)	\(nums[0] == 1\)，正确	`[1, -1, 3, 4]`
9	查漏 \(i=1\)	\(nums[1] = -1 \ne 2\)！发现首个缺失正整数为 2，直接返回！	`[1, -1, 3, 4]`

3. 动态集合 MEX 维护 (Dynamic MEX)¶

在实时数据流或交互式场景中，集合需要支持高频的插入元素、删除元素，并在 \(\mathcal{O}(1)\) 或 \(\mathcal{O}(\log N)\) 时间内查询当前集合的 MEX。

3.1 基于权值线段树的动态维护¶

利用权值线段树维护值域 \([0, M]\) 内每个数值出现的频次（Count）：

线段树的每个节点记录该值域区间内出现次数为 0 的最小数值，或直接维护区间内元素的最小计数值（min_cnt）；
若左子树的 min_cnt == 0，说明缺失值必在左半区间；否则左半区间已被完全填满，缺失值必在右半区间；
单次插入 insert(x) 和删除 erase(x) 耗时 \(\mathcal{O}(\log M)\)，查询 query_mex() 耗时严格 \(\mathcal{O}(\log M)\)。

3.2 基于 `std::set` 与频次数组的高性能轻量实现¶

若只关心 MEX 运算，由于有界性原理，我们只需维护可能成为 MEX 的缺失值集合：

维护一个全局哈希表或计数数组 cnt 记录各数值的出现次数；
维护一个 std::set<int> missing（或优先队列 / 小顶堆），预先放入所有当前计数为 0 的候选非负整数；
每次插入 \(x\)：若 cnt[x] == 0，将 \(x\) 从 missing 中擦除；然后 cnt[x]++；
每次删除 \(x\)：cnt[x]--；若减至 0，则将 \(x\) 插入回 missing；
查询 MEX：直接读取 *missing.begin() 即可，时间复杂度 \(\mathcal{O}(1)\)！

#include <vector>
#include <set>
#include <unordered_map>

class DynamicMEX {
private:
    std::unordered_map<int, int> count;
    std::set<int> missing; // 当前频次为 0 的非负候选值
    int max_val;

public:
    DynamicMEX(int capacity = 200005) : max_val(capacity) {
        for (int i = 0; i <= max_val; ++i) {
            missing.insert(i);
        }
    }

    void insert(int x) {
        if (x < 0) return;
        if (++count[x] == 1) {
            missing.erase(x);
        }
    }

    void erase(int x) {
        if (x < 0 || count.find(x) == count.end()) return;
        if (--count[x] == 0) {
            count.erase(x);
            missing.insert(x);
        }
    }

    int get_mex() const {
        return *missing.begin();
    }
};

4. 区间 MEX 查询 (Range MEX Queries)¶

4.1 问题模型¶

给定长度为 \(N\) 的数组 \(A\) 和 \(Q\) 次离线询问，每次询问给定区间 \([L, R]\)，要求输出子数组 \(A[L \dots R]\) 的 MEX。

4.2 离线扫描线 + 权值线段树二分定理¶

朴素计算单次需要 \(\mathcal{O}(R - L)\)，总体将退化至 \(\mathcal{O}(N \cdot Q)\)。经典高效解法为离线扫描线（Sweep-Line）结合权值线段树。

核心判定引理：在前缀区间 \(A[1 \dots R]\) 中，数值 \(v\) 出现在区间 \(A[L \dots R]\) 之内，当且仅当数值 \(v\) 在前缀中最后一次出现的下标 \(\text{last\_pos}[v] \ge L\)。

反之，数值 \(v\) 未在区间 \(A[L \dots R]\) 内出现，当且仅当 \(\text{last\_pos}[v] < L\)。

因此，区间 \(A[L \dots R]\) 的 MEX 等价于：

\[ \text{mex}(A[L \dots R]) = \min \{ v \ge 0 \mid \text{last\_pos}[v] < L \} \]

算法执行步骤：¶

离线排序：将所有查询按右端点 \(R\) 从小到大升序排序；
权值线段树定义：
线段树叶子节点 \(v \in [0, N]\) 存储数值 \(v\) 当前最后出现的下标 \(\text{last\_pos}[v]\)（初始未出现时为 \(-1\) 或 \(0\)）；
内部节点维护对应值域区间的最小值（tree[p] = min(tree[left], tree[right])）；
扫描线右移：
遍历下标 \(R\) 从 \(1\) 到 \(N\)，设当前数值为 \(x = A[R]\)；
若 \(x \le N\)，在线段树中将叶子 \(x\) 的位置更新为 \(R\)；
对于所有以当前 \(R\) 为右边界的查询 \((L, R)\)：
- 在权值线段树上进行树上二分（Binary Search on Segment Tree）：
- 检查左子树的最小值是否 \(< L\)：
- 若左子树最小值 \(< L\)，说明左半值域内必定存在某个数值最后一次出现的位置落在此区间左侧（即区间内不存在该数），答案必定在左子树；
- 若左子树最小值 \(\ge L\)，说明左半值域的所有数都在 \([L, R]\) 内至少出现过一次，答案必定在右子树；
- 递归下潜至叶子节点即为答案。
复杂度：总时间复杂度严格为 \(\mathcal{O}((N + Q) \log N)\)，空间复杂度 \(\mathcal{O}(N)\)。

#include <vector>
#include <algorithm>

struct Query {
    int l, r, id;
};

class RangeMEX {
private:
    int max_v;
    std::vector<int> tree; // 维护值域区间内 last_pos 的最小值

    void update(int node, int l, int r, int val, int pos) {
        if (l == r) {
            tree[node] = pos;
            return;
        }
        int mid = l + (r - l) / 2;
        if (val <= mid) update(2 * node, l, mid, val, pos);
        else update(2 * node + 1, mid + 1, r, val, pos);
        tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
    }

    // 在线段树上二分查找最小的 val 满足 last_pos[val] < L
    int query_first_less_than(int node, int l, int r, int L) {
        if (l == r) return l;
        int mid = l + (r - l) / 2;
        if (tree[2 * node] < L) {
            return query_first_less_than(2 * node, l, mid, L);
        } else {
            return query_first_less_than(2 * node + 1, mid + 1, r, L);
        }
    }

public:
    RangeMEX(int n) : max_v(n + 1), tree(4 * (n + 2), -1) {}

    static std::vector<int> solve(const std::vector<int> &a, std::vector<Query> &queries) {
        int n = a.size();
        int q = queries.size();
        std::vector<int> ans(q);

        // 按右端点升序离线排序
        std::vector<int> q_ids(q);
        for (int i = 0; i < q; ++i) q_ids[i] = i;
        std::sort(q_ids.begin(), q_ids.end(), [&](int i, int j) {
            return queries[i].r < queries[j].r;
        });

        RangeMEX solver(n);
        int cur_r = 0;
        for (int id : q_ids) {
            const auto &query = queries[id];
            while (cur_r <= query.r) {
                if (a[cur_r] <= n + 1) {
                    solver.update(1, 0, solver.max_v, a[cur_r], cur_r);
                }
                cur_r++;
            }
            ans[id] = solver.query_first_less_than(1, 0, solver.max_v, query.l);
        }
        return ans;
    }
};

5. 树上子树 MEX (Tree Subtree MEX)¶

在树形结构中，若需要为树上的每一个节点计算以其为根的子树所有权值的 MEX，常规做法需要借助树上启发式合并（DSU on Tree），在 \(\mathcal{O}(N \log N)\) 内完成。

而在特殊竞赛场景下（如元素互异，且基因值从 1 开始），存在极具代表性的自底向上路径爬升法：

自底向上单调指针优化 (LeetCode 2003 模型)¶

当树中所有节点的权值互不相同且为正整数时：

关键性质：数值 \(1\) 在整棵树中最多只出现一次！
对于任何不包含数值 \(1\) 的子树，其缺失的最小正整数必定为 \(1\)；
只有从“包含数值 \(1\) 的节点”一路向上到达根节点的唯一祖先链上的所有节点，其子树 MEX 才有可能严格大于 \(1\)；
爬升算法：
初始化全树节点的答案为 \(1\)；
找到基因值为 \(1\) 的节点，若不存在则全树均为 \(1\)，直接返回；
从该节点出发，沿着父指针逐级向上遍历到根节点：
- 在遍历到祖先节点 \(u\) 时，将 \(u\) 的其他未访问过的子树进行轻量 DFS 遍历，将其子树内的所有基因值标记为已出现；
- 维护一个全局单调自增的指针 mex（从 1 开始）：while (visited[mex]) ++mex;
- 节点 \(u\) 的答案即为当前的 mex 值。
复杂度分析：每个树节点最多被 DFS 遍历一次，mex 最多自增至 \(N+2\)，算法总时间复杂度严格为线性 \(\mathcal{O}(N)\)！

6. 博弈论中的 MEX 与 Sprague-Grundy (SG) 定理¶

MEX 是组合博弈论中分析公平无偏博弈（Impartial Combinatorial Game, ICG）的核心工具。

6.1 SG 函数的定义¶

在有向无环图（DAG）博弈模型中，对于任意游戏状态（图中的顶点）\(u\)，其 Sprague-Grundy 函数值定义为所有后继状态 SG 值的 MEX：

\[ SG(u) = \text{mex} \{ SG(v) \mid u \to v \} \]

终局状态（无法进行任何合法操作的状态）：没有后继状态，后继 SG 值集合为空，故 \(SG(\text{terminal}) = \text{mex}(\emptyset) = 0\)；
必败态（P-position）：\(SG(u) = 0\)（先手必败，后手必胜）；
必胜态（N-position）：\(SG(u) > 0\)（先手必胜，可转移到某个 \(SG = 0\) 的必败后继态）。

6.2 游戏和定理 (Nim 异或和)¶

由几个独立的子游戏复合而成的复合博弈 \(G = G_1 + G_2 + \dots + G_k\)，其整体状态的 SG 值为各子游戏 SG 值的按位异或和（Nim-Sum）：

\[ SG(G) = SG(G_1) \oplus SG(G_2) \oplus \dots \oplus SG(G_k) \]

先手必胜当且仅当 \(SG(G) \ne 0\)。通过打表观察单堆游戏的 SG 值规律，常能秒杀各类复杂的取石子变种博弈题。

7. LeetCode 经典 MEX 好题与深度精析¶

LeetCode 41 - 缺失的第一个正数 (First Missing Positive) 困难
提示

原地哈希置换归位的教科书级典范（详细题解见上文 2.4 节）。
- 题目要求严格 \(\mathcal{O}(N)\) 时间与 \(\mathcal{O}(1)\) 额外空间，寻找最小正整数（\(1\)-indexed MEX）。
- 核心 Intuition：由抽屉原理知缺失正整数必在 \([1, N+1]\) 内，数组之外的大数和负数均为杂质；借用原数组作为 \(N\) 个座位的“考勤表”，让数值 \(x\) 对号入座归位到下标 \(x - 1\)。
- 防死循环死穴：while 条件必须判断目标槽位是否已有正确副本 nums[nums[i] - 1] != nums[i]，严禁写成 nums[i] != i + 1，避免在重复元素（如 [1, 1]）下无限死循环。
- 势能分析：每次有效交换至少令一个数永久归位，全局交换次数 \(\le N\)，总时间复杂度严格 \(\mathcal{O}(N)\)。扫描首个 nums[i] != i + 1 即为答案 \(i + 1\)。
LeetCode 2003 - 每棵子树内缺失的最小基因值 (Smallest Missing Genetic Value in Each Subtree) 困难
提示

树上子树 MEX + 祖先链单调爬升。
- 节点基因值互异且均为正整数。若某子树不含基因值 \(1\)，则该子树的缺失最小正整数必为 \(1\)。
- 只有包含节点 \(1\) 的祖先链上的子树才需要额外计算。
- 从基因值为 \(1\) 的节点自底向上爬到根节点：
- 沿途对兄弟子树做 DFS，将其中所有节点的基因值计入全局 has 标记；
- 维护全局 mex 从 1 开始不断 while (has[mex]) mex++；
- 当前祖先的答案即为该 mex。每个节点至多被访问一次，总时间复杂度严格 \(\mathcal{O}(N)\)。
LeetCode 2598 - 执行操作后的最大 MEX (Smallest Missing Non-negative Integer After Operations) 中等
提示

模运算同余分组 + 木桶短板闭式求解（优于逐位模拟）。
- 任意次加减 value 表明：数值仅取决于其模 value 的非负余数 \(r = (x \pmod{value} + value) \pmod{value}\)。
- 轮次与木桶短板本质：构造连续整数 \(0, 1, 2, \dots\) 相当于按轮次推进。第 \(k\) 轮需要余数 \(0 \sim value-1\) 各出一个配额；
- 因此，能够完整拼凑出的完整轮数严格由频次最少的余数（木桶最短板）卡死：
\[ minR = \min_{0 \le i < value} count[i] \]
- 这 \(minR\) 轮直接贡献了前 \(minR \times value\) 个数；
- 在第 \(minR + 1\) 轮中，各余数消耗盈余。从 \(0\) 开始扫描，第一个频次恰好等于 \(minR\)（即无额外盈余）的余数下标 \(i\)，就是链条断裂的位置！
- 答案可直接闭式返回：\(ans = minR \times value + i\)。无需任何递减模拟，时间复杂度严格 \(\mathcal{O}(N + value)\)，空间复杂度 \(\mathcal{O}(value)\)。
LeetCode 1539 - 第 k 个缺失的正整数 (Kth Missing Positive Number) 简单
提示

广义 MEX 推广 + 单调性二分查找。
- 在递增正整数数组中，对于位置 \(mid\)，原本完整的连续序列在此处应当是 \(mid + 1\)。因此在 \(arr[mid]\) 之前缺失的正整数个数恰好为：
\[ \text{missing}(mid) = arr[mid] - (mid + 1) \]
- 由于数组严格递增，\(\text{missing}(mid)\) 具有严格的单调不降性。
- 二分查找最后一个满足 \(\text{missing}(mid) < k\) 的下标 \(mid\)。
- 答案即为 \(arr[mid] + (k - \text{missing}(mid)) = mid + 1 + k\)。时间复杂度 \(\mathcal{O}(\log N)\)。
LeetCode 2195 - 向数组中追加 K 个整数 (Append K Integers With Minimal Sum) 中等
提示

连续缺失区间的等差数列求和。
- 要求添加 \(K\) 个未在数组中出现的正整数使得和最小。贪心策略必是依次填入最小的 \(K\) 个缺失数（即广义 MEX 序列的前 \(K\) 项）。
- 将数组排序并去重。顺序扫描相邻两数之间的空隙 \([prev + 1, curr - 1]\)：
- 若区间长度 \(len = curr - prev - 1 > 0\)，可容纳的数字个数为 \(take = \min(K, len)\)；
- 利用等差数列求和公式将这 \(take\) 个数的和加入答案，并更新 \(K \leftarrow K - take\)；
- 若扫描结束 \(K\) 仍大于 0，直接在数组最大值之后追加连续的 \(K\) 个数。时间复杂度 \(\mathcal{O}(N \log N)\)。
LeetCode 268 - 丢失的数字 (Missing Number) 简单
提示

经典 MEX 入门的三种武器。
- 数组包含 \(0 \sim n\) 中缺失了一个数字的 \(n\) 个数。
- 解法一（高斯求和公式）：全集和 \(\frac{n(n+1)}{2}\) 减去数组所有元素和，差值即为缺失数；
- 解法二（异或消除法）：利用 \(x \oplus x = 0\) 和 \(x \oplus 0 = x\)，将 \(0 \sim n\) 的所有数与数组中的所有数整体异或，成对的数全部抵消，最终剩下的就是缺失数；
- 解法三（原地标记法）：将每个数归位到对应下标。
LeetCode 2009 - 使数组连续的最少操作数 (Minimum Number of Operations to Make Array Continuous) 困难
提示

值域定长窗口内的补齐缺失量。
- 最终连续数组的长度必须为 \(N\)，其元素覆盖一个长度为 \(N\) 的区间 \([x, x + N - 1]\)。
- 将原数组去重并升序排序，得到不重复数组 \(A\)。
- 遍历每个元素作为连续区间的起始左端点 \(A[i]\)，利用二分（std::upper_bound）或滑动窗口找到落入 \([A[i], A[i] + N - 1]\) 范围内的已有元素个数 \(count\)。
- 需要替换的操作次数即为 \(N - count\)。取全局最小值即可，时间复杂度 \(\mathcal{O}(N \log N)\)。
LeetCode 2663 - 字典序最小的美丽字符串 (Lexicographically Smallest Beautiful String) 困难
提示

字符集上的局部 MEX 贪心构造。
- 不包含长度 \(\ge 2\) 的回文子串，等价于对任意位置 \(i\)，必须满足 \(s[i] \ne s[i-1]\) 且 \(s[i] \ne s[i-2]\)（禁止长度为 2 和 3 的对称串）。
- 从末尾向前寻找第一个可以增大的字符 \(s[i]\)：
- 新字符 \(c > s[i]\) 必须在前 \(k\) 个小写字母内，且不能与 \(s[i-1]\) 和 \(s[i-2]\) 相同（在可用字符集中选取排除前两个字符后的局部 MEX 最小候选）；
- 找到后将其放入位置 \(i\)，随后对于 \(i+1 \dots n-1\) 的所有后续位置，贪心地选用不等于前两位字符的全局最小字符（再次运用局部 MEX，从 'a' 开始选取）。时间复杂度 \(\mathcal{O}(N)\)。