Kimi LeetCode 3948. 字典序最大的 MEX 数组 Java实现
以下是 LeetCode 3948. 字典序最大的 MEX 数组 的 Java 实现。思路贪心 双指针1. 预处理后缀 MEX从数组末尾往前遍历用 HashSet 维护已出现的数同时维护当前 MEX得到 suf[i] 表示从位置 i 开始到末尾的后缀的 MEX。2. 双指针构造答案从左到右每次取 target suf[idx] 作为当前位的最大可能 MEX- 若 target 0直接取一个元素答案加 0。- 若 target 0找到最短的包含 [0, target-1] 的前缀将其 MEX即 target加入答案并跳到该前缀之后继续。时间复杂度O(n)每个元素最多被访问两次。空间复杂度O(n)。javaimport java.util.*;class Solution {public int[] maximumMEX(int[] nums) {int n nums.length;// 1. 预处理后缀 MEXsuf[i] 表示 nums[i..n-1] 的 MEXint[] suf new int[n];SetInteger set new HashSet();int mex 0;for (int i n - 1; i 0; i--) {set.add(nums[i]);while (set.contains(mex)) {mex;}suf[i] mex;}// 2. 双指针贪心构造字典序最大的 resultListInteger ans new ArrayList();int idx 0;while (idx n) {int target suf[idx]; // 当前能取到的最大 MEXint right idx;if (target 0) {// 找最短前缀使其包含 0,1,...,target-1SetInteger cur new HashSet();int curMex 0;while (right n curMex target) {cur.add(nums[right]);while (cur.contains(curMex)) {curMex;}right;}ans.add(curMex); // curMex target} else {// target 0每次取一个元素即可right;ans.add(0);}idx right;}int[] res new int[ans.size()];for (int i 0; i ans.size(); i) {res[i] ans.get(i);}return res;}}示例验证输入 过程 输出nums [0,1,0] 后缀 MEX: [2,2,1] → 先取 [0,1] MEX2再取 [0] MEX1 [2,1]nums [1,0,2] 后缀 MEX: [3,1,0] → 取全部 [1,0,2] MEX3 [3]nums [3,1] 后缀 MEX: [0,0] → 每次取一个MEX 均为 0 [0,0]
