针对 LeetCode 3830“移除至多一个元素后的最长交替子数组”这里提供两种 Python3 解法动态规划 (O(n) 时间, O(1) 空间) 和前后缀分解 (O(n) 时间, O(n) 空间)。---解法一动态规划推荐维护 4 个状态用滚动变量实现无需数组。状态含义以当前元素结尾· inc0最后一段比较为 上升未删除元素· dec0最后一段比较为 下降未删除元素· inc1最后一段比较为 上升已删除一个元素· dec1最后一段比较为 下降已删除一个元素每个状态初始为 1仅包含当前元素本身。转移遍历 i 从 1 到 n-11. 正常延续不删除 i-1· 若 nums[i] nums[i-1]上升· inc0 dec0_prev 1· inc1 dec1_prev 1· 若 nums[i] nums[i-1]下降· dec0 inc0_prev 1· dec1 inc1_prev 12. 删除 i-1使用一次删除机会· 需要 i 2比较 nums[i] 与 nums[i-2]· 若 nums[i] nums[i-2]上升· inc1 max(inc1, dec0_prev2 1)· 若 nums[i] nums[i-2]下降· dec1 max(dec1, inc0_prev2 1)3. 每个状态至少为 1重新开始。Python 代码pythonclass Solution:def longestAlternating(self, nums: List[int]) - int:n len(nums)if n 0:return 0# 初始化 i0 的状态inc0 dec0 inc1 dec1 1ans 1# 用于保存 i-2 状态的变量初始不存在设为0inc0_prev2 dec0_prev2 0for i in range(1, n):# 保存当前状态作为下一次的 prev2next_inc0_prev2 inc0next_dec0_prev2 dec0# 保存 prev1prev_inc0, prev_dec0 inc0, dec0prev_inc1, prev_dec1 inc1, dec1# 重置当前状态每个状态至少为1inc0 dec0 inc1 dec1 1# 正常延续不删除 i-1if nums[i] nums[i-1]:inc0 max(inc0, prev_dec0 1)inc1 max(inc1, prev_dec1 1)elif nums[i] nums[i-1]:dec0 max(dec0, prev_inc0 1)dec1 max(dec1, prev_inc1 1)# 删除 i-1跳过中间元素if i 2:if nums[i] nums[i-2]:inc1 max(inc1, dec0_prev2 1)elif nums[i] nums[i-2]:dec1 max(dec1, inc0_prev2 1)# 更新答案ans max(ans, inc0, dec0, inc1, dec1)# 更新 prev2 为旧的状态即 i-1 的状态inc0_prev2 next_inc0_prev2dec0_prev2 next_dec0_prev2return ans---解法二前后缀分解更直观步骤1. 前缀数组 pref[i]以 i 结尾的最长交替子数组长度不删除。2. 后缀数组 suff[i]以 i 开头的最长交替子数组长度不删除。3. 答案候选· 不删除max(pref[i])· 删除位置 i1 i n-2若能合并尝试 pref[i-1] suff[i1]Python 代码pythonclass Solution:def longestAlternating(self, nums: List[int]) - int:n len(nums)if n 0:return 0# 计算前缀pref [1] * nfor i in range(1, n):if i 1:pref[i] 2 if nums[i] ! nums[i-1] else 1else:# 检查 nums[i-2] 和 nums[i-1] 以及 nums[i-1] 和 nums[i] 是否交替if (nums[i-2] nums[i-1] nums[i]) or (nums[i-2] nums[i-1] nums[i]):pref[i] pref[i-1] 1else:pref[i] 2 if nums[i] ! nums[i-1] else 1# 计算后缀suff [1] * nfor i in range(n-2, -1, -1):if i n-2:suff[i] 2 if nums[i] ! nums[i1] else 1else:if (nums[i] nums[i1] nums[i2]) or (nums[i] nums[i1] nums[i2]):suff[i] suff[i1] 1else:suff[i] 2 if nums[i] ! nums[i1] else 1ans max(pref suff) # 不删除的情况# 枚举删除位置 i1 i n-2for i in range(1, n-1):can_merge Falseif i 1:# 左边只有一个元素只需 nums[i-1] 和 nums[i1] 不等can_merge (nums[i-1] ! nums[i1])else:# 检查三元组 (nums[i-2], nums[i-1], nums[i1]) 是否满足交替# 可能模式: nums[i-2] nums[i-1] nums[i1]# 或 nums[i-2] nums[i-1] nums[i1]if (nums[i-2] nums[i-1] and nums[i-1] nums[i1]) or \(nums[i-2] nums[i-1] and nums[i-1] nums[i1]):can_merge Trueif can_merge:ans max(ans, pref[i-1] suff[i1])return ans---两种解法对比特性 DP 解法 前后缀分解时间复杂度 O(n) O(n)空间复杂度 O(1) O(n)代码复杂度 状态多需仔细 逻辑清晰适用场景 内存受限 面试/日常优先建议竞赛或内存敏感场景用 DP面试或需要快速实现用前后缀分解。如有任何疑问欢迎继续交流