以下是 LeetCode 3948. 字典序最大的 MEX 数组 的 JavaScript 实现基于贪心 双指针策略时间复杂度 O(n)。解题思路核心贪心策略1. 后缀 MEX 预处理从右往左扫描数组计算每个位置开始的后缀的 MEX 值。这个值就是当前步骤能取到的最大 MEX。2. 最短前缀截取对于当前位置如果后缀 MEX target- 若 target 0需要找到最短的前缀使得该前缀包含 0, 1, ..., target-1 所有数。这样可以保留尽可能多的元素给后续步骤。- 若 target 0直接取一个元素MEX 就是 0。3. 重复直到数组为空。JavaScript 实现javascript/*** param {number[]} nums* return {number[]}*/var maximumMEX function(nums) {const n nums.length;// 预处理后缀 MEXconst suf new Array(n);const seen new Set();let mex 0;for (let i n - 1; i 0; i--) {seen.add(nums[i]);while (seen.has(mex)) {mex;}suf[i] mex;}let idx 0;const ans [];while (idx n) {const target suf[idx]; // 当前能取到的最大 MEXlet right idx;const seenLocal new Set();let curMex 0;if (target 0) {// 找到最短前缀包含 0, 1, ..., target-1while (right n curMex target) {seenLocal.add(nums[right]);while (seenLocal.has(curMex)) {curMex;}right;}} else {// target 0直接取一个元素right;}ans.push(curMex);idx right;}return ans;};复杂度分析项目 复杂度 说明时间复杂度 O(n) 每个元素最多被访问常数次空间复杂度 O(n) 后缀 MEX 数组 两个 Set示例验证输入 输出 解释[0, 1, 0] [2, 1] 先取 [0,1] MEX2再取 [0] MEX1[1, 0, 2] [3] 取全部MEX3[3, 1] [0, 0] 无 0每次取一个 MEX 都是 0[0, 1, 2, 3] [4] 包含 0,1,2,3MEX4[3, 2, 1, 0, 1, 2, 1] [4, 0, 0, 0] 先取到 0 时凑齐 0,1,2,3后续无 0 则 MEX0关键点说明1. 为什么后缀 MEX 是最大值 因为无论怎么选前缀剩余后缀的 MEX 不可能超过整个后缀的 MEX。2. 为什么要最短前缀 字典序要求结果数组尽可能长在 MEX 相同的情况下更长的数组字典序更大所以要保留更多元素。3. target 0 的特殊处理当后缀中没有 0 时任何前缀的 MEX 都是 0此时逐个取元素可以得到最多的 0字典序最优。