2026-09-08：字典序最大的 MEX 数组。用go语言，给定一个整数数组，我们需要通过重复操作将其全部截取完毕，并在每一步构造出一个新数组

2026-09-08：字典序最大的 MEX 数组。用go语言，给定一个整数数组，我们需要通过重复操作将其全部截取完毕，并在每一步构造出一个新数组。每一步的操作规则是：先选定一个正整数 k，其值不能超过当前数组剩余的长度；然后取出当前数组开头的 k 个元素，计算出这 k 个数中的 MEX（即缺失的最小非负整数）；把这个 MEX 数值依次追加到结果数组中；接着从原数组中删掉刚刚取出的这 k 个元素。整个过程持续到原数组为空为止。我们的最终目标，是通过每一步合理选择 k 的取值，使得最后得到的结果数组在字典序上尽可能大。字典序的比较方式是从前往后逐个对比元素，第一次出现不同时，数值较大的数组更优；如果较短数组的所有元素都能与较长数组的对应位置完全一致，那么长度更长的数组视为更大。

1 <= nums.length <= 100000。

0 <= nums[i] <= 100000。

输入： nums = [0,1,0]。

输出： [2,1]。

解释：

取前 k = 2 个元素 [0, 1]，其 MEX = 2。当前 result = [2]。

剩余数组 [0] 的 MEX = 1。因此，最终的 result = [2, 1]。

题目来自力扣3948。

一、预处理阶段

1. 1. 设原数组长度为n。因为 MEX 最大不可能超过n（即使数组包含0..n-1所有数，MEX 也仅为n），所以所有大于等于n的数对于 MEX 的计算没有任何影响，直接忽略。

2. 2. 创建一个pos结构，pos[x]是一个列表，用来存储原数组中所有值等于x的下标（仅存储x < n的情况）。

• • 遍历原数组，如果nums[i] < n，就把下标i加入pos[nums[i]]。

3. 为了后续方便地找到某个值在当前剩余数组中最靠左的位置，把每个pos[x]列表反转，使得列表的末尾存放的是该值在原数组中的最小下标。这样每次只需要查看列表末尾，即可得到当前剩余数组中最左边的x的位置，并且可以用pop操作快速移除已经不在剩余数组中的旧下标。

二、主循环：逐段确定最大 MEX

用变量i表示当前剩余数组的起始下标（在原数组中的位置）。初始时i = 0。

只要i < n，就说明还有元素未被截取，开始构造下一段：

1. 1.设置当前段的起点
   start = i，表示这一段从原数组的start位置开始。

2. 2.从mex = 0开始尝试扩展当前段的 MEX
   不断检查当前剩余数组中是否存在值mex：

   这个过程相当于：从0开始，只要能找到0、1、2…… 就不断把段向右扩展，直到遇到第一个缺失的值。最终得到的mex就是当前段能够达到的最大 MEX。

• • 取出pos[mex]列表。

• •清理过期下标：
  弹出列表末尾所有小于start的下标。这些下标属于已经被之前段截掉的部分，不再属于当前剩余数组。清理之后，列表末尾就是当前剩余数组中值mex的最左位置（如果存在的话）。

• • 如果清理后列表为空，说明当前剩余数组中已经不存在值mex，因此当前段的 MEX 最大就是mex，跳出循环。

• • 如果列表非空，说明当前剩余数组中存在值mex。为了让当前段包含这个值，段必须至少延伸到该值在当前剩余数组中最左的位置。因此，如果该位置大于当前段的右边界i，就更新i为该位置。

• • 然后mex += 1，继续检查下一个值是否能被包含进当前段。

3.记录结果并进入下一段
将得到的mex追加到结果数组ans中。
当前段覆盖的原数组区间是[start, i]（其中i是扩展后的右边界）。删除这一段后，剩余数组从i + 1开始。
所以执行i++，继续下一轮外层循环。

三、示例说明

以输入nums = [0, 1, 0]为例：

• • 预处理：

• • •pos[0] = [0, 2]，反转后为[2, 0]

  • •pos[1] = [1]

  • •pos[2] = []

• • 第一段：

• • •start = 0，i = 0，mex = 0

  • •pos[0]末尾是0，不小于start，保留。i仍为0。mex=1

  • •pos[1]末尾是1，不小于start，保留。1 > i，更新i = 1。mex=2

  • •pos[2]为空，跳出。得到 MEX = 2。
    第一段为[0, 1]，结果[2]，删除后i = 2。

• • 第二段：

• • •start = 2，i = 2，mex = 0

  • •pos[0]末尾是0，小于start=2，弹出；新末尾为2，不小于start，保留。i仍为2。mex=1

  • •pos[1]末尾是1，小于start=2，弹出，列表空，跳出。得到 MEX = 1。
    第二段为[0]，结果追加1，最终[2, 1]。

• •预处理：遍历原数组一次，并将部分下标加入pos，然后反转所有列表，总耗时为O(n)。

• •主循环：

• • • 外层i从0递增到n，最多执行n次。

  • • 内层对mex的检查中，每个下标在清理时最多被弹出一次，所有pos列表的元素总数不超过n，所以总弹出操作为O(n)。

  • • 另外，每一段中mex从0递增到该段的 MEX。由于每段的 MEX 不超过该段的长度，而所有段的长度之和为n，所以所有段的 MEX 之和也不超过n。因此内层mex递增的总次数也是O(n)。

综上，总时间复杂度为 O(n)。

五、额外空间复杂度分析

• •pos结构存储了所有值小于n的元素下标，这些下标总数不超过n，所以存储这些下标的额外空间为O(n)。

• •ans结果数组最多包含n个元素，也是O(n)。

• • 其他辅助变量和切片头开销均为常数或O(n)级别。

因此，总的额外空间复杂度为 O(n)。

Go完整代码如下：

package main

 import "fmt"

 func maximumMEX(nums []int) []int {
    n := len(nums)
    // mex 最大是 n，>= n 的数无需考虑
    pos := make([][]int, n+1) // n 作为哨兵
    for i, x := range nums {
        if x < n {
            pos[x] = append(pos[x], i)
        }
    }
    // 反转每个列表，使最小索引位于末尾，便于弹出
    for _, p := range pos {
        for i, j := 0, len(p)-1; i < j; i, j = i+1, j-1 {
            p[i], p[j] = p[j], p[i]
        }
    }

     ans := []int{}
    i := 0
    for i < n {
        start := i // 这一段的起点
        mex := 0
        for {
            q := pos[mex]
            // 清理在 start 之前的下标（末尾是最小索引）
            for len(q) > 0 && q[len(q)-1] < start {
                q = q[:len(q)-1]
            }
            pos[mex] = q
            if len(q) == 0 {
                break
            }
            // 这一段包含剩余元素中的最左边的 mex
            if q[len(q)-1] > i {
                i = q[len(q)-1]
            }
            mex++
        }
        ans = append(ans, mex)
        i++
    }
    return ans
}

 func main() {
    nums := []int{0, 1, 0}
    result := maximumMEX(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def maximumMEX(nums):
    n = len(nums)
    # mex 最大是 n，>= n 的数无需考虑
    pos = [[] for _ in range(n + 1)]  # n 作为哨兵
    for i, x in enumerate(nums):
        if x < n:
            pos[x].append(i)
    # 反转每个列表，使最小索引位于末尾，便于弹出
    for p in pos:
        p.reverse()
    ans = []
    i = 0
    while i < n:
        start = i  # 这一段的起点
        mex = 0
        while True:
            q = pos[mex]
            # 清理在 start 之前的下标（末尾是最小索引）
            while q and q[-1] < start:
                q.pop()
            if not q:
                break
            # 这一段包含剩余元素中的最左边的 mex
            if q[-1] > i:
                i = q[-1]
            mex += 1
        ans.append(mex)
        i += 1
    return ans

 # 测试
if __name__ == "__main__":
    nums = [0, 1, 0]
    result = maximumMEX(nums)
    print(result)  

C++完整代码如下：

  

    

using namespace std;


 vector maximumMEX(vector& nums) {
    int n = nums.size();
    vector 
 
 int 
 >> pos(n +  
 1 
 ); 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < n; ++i) { 
 
 
          
 int 
  x = nums[i]; 
 
 
          
 if 
  (x < n) { 
 
 
             pos[x].push_back(i); 
 
 
         } 
 
 
     } 
 
 
      
 // 反转每个列表，使最小索引位于末尾 
 
 
      
 for 
  (auto& p : pos) { 
 
 
         reverse(p.begin(), p.end()); 
 
 
     } 
 
 
 
 
     vector< 
 int 
 > ans; 
 
 
      
 int 
  i =  
 0 
 ; 
 
 
     while (i < n) { 
 
 
          
 int 
  start = i; 
 
 
          
 int 
  mex =  
 0 
 ; 
 
 
         while ( 
 true 
 ) { 
 
 
              
 // 清理在 start 之前的下标（末尾是最小索引） 
 
 
             while (!pos[mex].empty() && pos[mex].back() < start) { 
 
 
                 pos[mex].pop_back(); 
 
 
             } 
 
 
              
 if 
  (pos[mex].empty()) { 
 
 
                  
 break 
 ; 
 
 
             } 
 
 
              
 // 这一段包含剩余元素中的最左边的 mex 
 
 
              
 if 
  (pos[mex].back() > i) { 
 
 
                 i = pos[mex].back(); 
 
 
             } 
 
 
             mex++; 
 
 
         } 
 
 
         ans.push_back(mex); 
 
 
         i++; 
 
 
     } 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums = { 
 0 
 ,  
 1 
 ,  
 0 
 }; 
 
 
     vector< 
 int 
 > result = maximumMEX(nums); 
 
 
      
 for 
  ( 
 int 
  x : result) { 
 
 
         cout << x <<  
 " " 
 ; 
 
 
     } 
 
 
     cout << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。