DeepSeek LeetCode 3830. 移除至多一个元素后的最长交替子数组 Python3实现-北京尧图网络

针对 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面试或需要快速实现用前后缀分解。如有任何疑问欢迎继续交流

DeepSeek LeetCode 3830. 移除至多一个元素后的最长交替子数组 Python3实现

相关推荐

AI技能化实战：从通用模型到专属工作流的构建指南

深入理解Python中的类方法、类实例方法和静态方法

FPGA验证必备：Vivado覆盖率分析从原理到实战

更多资讯

2026年国内Claude API聚合平台实测：词元之河企业级稳定调用表现领跑

docker-k8s安装实践记录

没有项目管理经验可以考PMP吗

元器猫硬件笔记：P沟道MOSFET NCE4435沟槽工艺国产化替代与实测验证

【八八股股 | 第二篇】Java注解原理

* LangChain 模型统一接入：ChatOpenAI 兼容用法与 init_chat_model 详解

今日更新

AI元人文：从工具使用到思维重构的深度探索

Python+CNN车牌识别实战：从数据预处理到模型训练与部署

Vim基础操作全攻略：保存退出、模式切换与高频命令实战

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？