以下是 LeetCode 3948. 字典序最大的 MEX 数组 的 Rust 实现rustimpl Solution {pub fn maximum_mex(nums: Veci32) - Veci32 {let n nums.len();let mut suf vec![0i32; n];// 1. 预处理后缀 MEXsuf[i] 表示子数组 nums[i..] 的 MEX// MEX 最大不超过 n1用 Vecbool 替代 HashSet 更高效let mut seen vec![false; n 2];let mut mex: usize 0;for i in (0..n).rev() {let x nums[i] as usize;if x seen.len() {seen[x] true;}while mex seen.len() seen[mex] {mex 1;}suf[i] mex as i32;}// 2. 贪心构造答案let mut ans Vec::new();let mut i 0;while i n {let target suf[i] as usize;// 若后缀 MEX 为 0说明没有 0取一个元素即可得到 0if target 0 {ans.push(0);i 1;continue;}// 向右扩展直到当前前缀包含 0, 1, ..., target-1// 只需追踪小于 target 的数let mut cur vec![false; target];let mut cmex: usize 0;while cmex target {let x nums[i] as usize;if x target {cur[x] true;}while cmex target cur[cmex] {cmex 1;}i 1;}ans.push(target as i32);}ans}}---核心思路步骤 说明后缀 MEX 预处理 从右向左扫描用布尔数组 seen 维护已出现的数suf[i] 记录子数组 nums[i..] 的 MEX贪心取最短前缀 若 suf[i] target则从 i 向右扩展收集齐 0..target-1 后立即断开。这样 append 了最大的 MEX同时留下尽可能多的元素给后续MEX 为 0 的特殊处理 若后缀中没有 0每次取一个元素 MEX 都是 0直接逐个取复杂度- 时间复杂度O(n)每个元素最多被处理两次- 空间复杂度O(n)后缀数组与辅助布尔数组