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

福大大架构师每日一题

发布于 2026-06-05 20:08:28

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++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestAlternating(vector<int>& a) {
    int n = a.size();
    // 创建三维数组 f[i][j][k]，初始化为1
    vector<vector<vector<int>>> f(n, vector<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;
    return0;
}