2026-06-05：移除至多一个元素后的最长交替子数组。用go语言，给你一个整数数组 nums。我们称某个连续片段（子数组）为“交替”，当它的

2026-06-05：移除至多一个元素后的最长交替子数组。用go语言，给你一个整数数组 nums。我们称某个连续片段（子数组）为“交替”，当它的相邻元素之间的大小关系严格交替出现：要么是“先上升再下降再上升……”（相邻比较依次为 <, >, <, > …），要么是“先下降再上升再下降……”（相邻比较依次为 >, <, >, < …）。单个元素的子数组也算交替。

你最多可以从数组中删除一个元素（删掉后剩余元素仍保持原相对顺序）。删除完成后，你需要在剩下的数组里选出一个交替子数组。

请返回：你能得到的最长交替子数组的长度。

2 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入： nums = [2,1,3,2]。

输出： 4。

解释：

选择不移除任何元素。

选择整个数组[2, 1, 3, 2]，这是交替的，因为2 > 1 < 3 > 2。

题目来自力扣3830。

解题过程分步详解 第一步：定义核心状态（理解三维数组f的含义）

代码中定义了三维数组f[i][x][y]，这是解题的核心，我们先明确每个维度的意义：

1.i：表示数组的第i个元素（从0开始计数）；

2.x：取值0/1，代表是否已经删除过元素

•x=0：到第i个元素为止，没有删除过任何元素；

•x=1：到第i个元素为止，已经删除过1个元素；

3.y：取值0/1，代表当前子数组的最后一步大小关系

•y=0：最后一步是下降（前一个元素 > 当前元素）；

•y=1：最后一步是上升（前一个元素 < 当前元素）；

4.f[i][x][y] 的值：以第i个元素结尾，满足「x删除状态」和「y大小关系」的最长交替子数组长度。

第二步：初始化状态

1. 数组长度n：示例中nums = [2,1,3,2]，n=4；

2. 初始化三维数组f：长度为n，所有位置的初始值都是1；

• 原因：单个元素本身就是一个长度为1的交替子数组，无论是否删除、无论大小关系，最小长度都是1；

3. 初始化答案ans=1：最短的交替子数组长度就是1。

第三步：遍历数组（从第2个元素开始，i从1到n-1）

遍历的核心逻辑：逐个检查每个元素，分两种情况更新最长长度——不删除元素、删除元素。

核心规则

交替子数组要求：当前的大小关系，必须和上一步的大小关系相反。
例：上一步是下降（y=0），下一步必须是上升（y=1）；上一步是上升（y=1），下一步必须是下降（y=0）。

情况1：不删除元素（相邻两个元素直接比较）

条件：a[i-1] != a[i]（相等无法形成交替，直接跳过）

1. 判断当前相邻元素的大小关系：

• 若a[i-1] < a[i]→ 标记inc=1（上升）；

• 若a[i-1] > a[i]→ 标记inc=0（下降）；

2. 状态更新：
当前大小关系是inc，上一步必须是相反的inc^1（异或运算，0变1，1变0）；

• 无删除（x=0）：f[i][0][inc] = 上一个元素无删除、相反关系的长度 + 1；

• 已删除1个（x=1）：f[i][1][inc] = 上一个元素已删除、相反关系的长度 + 1；

情况2：删除一个元素（跳过i-1元素，直接比较i-2和i）

条件：i>1（至少有3个元素才能删除中间的i-1）且a[i-2] != a[i]

1. 判断a[i-2]和a[i]的大小关系，得到inc；

2. 状态更新：
这一步消耗了删除次数，所以只更新x=1（已删除）的状态；
用i-2元素、无删除、相反关系的长度 +1，和当前值取最大；

第四步：更新最终答案

每遍历一个元素i，就用当前f[i][1][0]和f[i][1][1]更新最大值ans：

•f[i][1][0/1]包含了无删除和删除1个元素两种场景的最优解；

• 遍历结束后，ans就是最终的最长长度。

示例[2,1,3,2]的完整执行过程

1.i=1（元素1）：
比较2和1，下降（inc=0）；
无删除：长度=2；已删除：长度=2；
ans更新为2。

2.i=2（元素3）：
① 不删除：比较1和3，上升（inc=1），上一步是下降，长度=3；
② 无需删除元素（i>1但直接交替已满足）；
ans更新为3。

3.i=3（元素2）：
① 不删除：比较3和2，下降（inc=0），上一步是上升，长度=4；
② 无需删除元素；
ans更新为4。

最终返回ans=4，符合题目要求。

时间复杂度 & 额外空间复杂度 1. 时间复杂度

• 代码只进行了一次数组遍历（循环从i=1到n-1）；

• 循环内的所有操作（比较、赋值、取最大值）都是O(1)的常数时间；

• 总时间复杂度：O(n)（n是数组长度），能满足题目n≤10⁵的性能要求。

2. 额外空间复杂度

• 代码创建了一个三维数组f，大小为n × 2 × 2；

• 2×2是固定常数，因此空间占用与数组长度n成正比；

• 总额外空间复杂度：O(n)。

总结

1. 核心思路：用三维状态数组记录「位置、是否删除、大小关系」，动态规划递推最长长度；

2. 遍历一次数组，分「不删除」「删除一个元素」两种场景更新状态；

3. 时间复杂度O(n)，空间复杂度O(n)，高效适配题目数据规模。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func longestAlternating(a []int)int {
    n := len(a)
    f := make([][2][2]int, n)
    for i := range f {
        f[i] = [2][2]int{{1, 1}, {1, 1}}
    }

     ans := 1
    for i := 1; i < n; i++ {
        if a[i-1] != a[i] {
            inc := 0
            if a[i-1] < a[i] {
                inc = 1
            }
            f[i][0][inc] = f[i-1][0][inc^1] + 1
            f[i][1][inc] = f[i-1][1][inc^1] + 1
        }
        if i > 1 && a[i-2] != a[i] {
            inc := 0
            if a[i-2] < a[i] {
                inc = 1
            }
            f[i][1][inc] = max(f[i][1][inc], f[i-2][0][inc^1]+1)
        }
        ans = max(ans, f[i][1][0], f[i][1][1])
    }
    return ans
}

 func main() {
    nums := []int{2, 1, 3, 2}
    result := longestAlternating(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

 def longest_alternating(a):
    n = len(a)
    # 创建三维数组 f[i][j][k]，使用嵌套列表推导式
    f = [[[1, 1], [1, 1]] for _ in range(n)]
    ans = 1
    for i in range(1, n):
        if a[i-1] != a[i]:
            inc = 1if a[i-1] < a[i] else0
            f[i][0][inc] = f[i-1][0][inc ^ 1] + 1
            f[i][1][inc] = f[i-1][1][inc ^ 1] + 1
        if i > 1 and a[i-2] != a[i]:
            inc = 1if a[i-2] < a[i] else0
            f[i][1][inc] = max(f[i][1][inc], f[i-2][0][inc ^ 1] + 1)
        ans = max(ans, f[i][1][0], f[i][1][1])
    return ans

 def main():
    nums = [2, 1, 3, 2]
    result = longest_alternating(nums)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  


 using namespace std;

 int longestAlternating(vector& a) {
    int n = a.size();
    // 创建三维数组 f[i][j][k]，初始化为1
    vector 
 
 int 
 >>> f(n, vector 
 
 int 
 >>( 
 2 
 , vector< 
 int 
 >( 
 2 
 ,  
 1 
 ))); 
 
 
 
 
      
 int 
  ans =  
 1 
 ; 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i < n; i++) { 
 
 
          
 if 
  (a[i 
 -1 
 ] != a[i]) { 
 
 
              
 int 
  inc = (a[i 
 -1 
 ] < a[i]) ?  
 1 
  :  
 0 
 ; 
 
 
             f[i][ 
 0 
 ][inc] = f[i 
 -1 
 ][ 
 0 
 ][inc ^  
 1 
 ] +  
 1 
 ; 
 
 
             f[i][ 
 1 
 ][inc] = f[i 
 -1 
 ][ 
 1 
 ][inc ^  
 1 
 ] +  
 1 
 ; 
 
 
         } 
 
 
          
 if 
  (i >  
 1 
  && a[i 
 -2 
 ] != a[i]) { 
 
 
              
 int 
  inc = (a[i 
 -2 
 ] < a[i]) ?  
 1 
  :  
 0 
 ; 
 
 
             f[i][ 
 1 
 ][inc] = max(f[i][ 
 1 
 ][inc], f[i 
 -2 
 ][ 
 0 
 ][inc ^  
 1 
 ] +  
 1 
 ); 
 
 
         } 
 
 
         ans = max({ans, f[i][ 
 1 
 ][ 
 0 
 ], f[i][ 
 1 
 ][ 
 1 
 ]}); 
 
 
     } 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums = { 
 2 
 ,  
 1 
 ,  
 3 
 ,  
 2 
 }; 
 
 
      
 int 
  result = longestAlternating(nums); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 

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