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

针对 LeetCode 3830“移除至多一个元素后的最长交替子数组”这里提供 Rust 实现采用动态规划 (O(n) 时间, O(1) 空间)代码高效且安全。---核心思路维护 4 个状态以当前元素结尾· inc0最后一段比较为上升 ()未删除元素· dec0最后一段比较为下降 ()未删除元素· inc1最后一段比较为上升已删除一个元素· dec1最后一段比较为下降已删除一个元素每个状态初始为 1仅包含当前元素本身。转移遍历 i 从 1 到 n-11. 正常延续不删除 i-1· 若 nums[i] nums[i-1]inc0 dec0_prev 1inc1 dec1_prev 1· 若 nums[i] nums[i-1]dec0 inc0_prev 1dec1 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重新开始。---Rust 代码实现rustimpl Solution {pub fn longest_alternating(nums: Veci32) - i32 {let n nums.len();if n 0 {return 0;}if n 1 {return 1;}// 初始状态以 nums[0] 结尾let (mut inc0, mut dec0) (1, 1);let (mut inc1, mut dec1) (1, 1);let mut ans 1;// 保存 i-2 时的未删除状态初始不存在设为 0let (mut inc0_prev2, mut dec0_prev2) (0, 0);for i in 1..n {// 保存当前状态作为下一轮迭代的 prev2let (next_inc0, next_dec0) (inc0, dec0);// 保存上一轮状态prev1let (prev_inc0, prev_dec0) (inc0, dec0);let (prev_inc1, prev_dec1) (inc1, dec1);// 重置当前状态至少为 1inc0 1;dec0 1;inc1 1;dec1 1;// ---- 正常延续不删除 i-1 ----if nums[i] nums[i - 1] {inc0 inc0.max(prev_dec0 1);inc1 inc1.max(prev_dec1 1);} else if nums[i] nums[i - 1] {dec0 dec0.max(prev_inc0 1);dec1 dec1.max(prev_inc1 1);}// ---- 删除 i-1跳过中间元素 ----if i 2 {if nums[i] nums[i - 2] {inc1 inc1.max(dec0_prev2 1);} else if nums[i] nums[i - 2] {dec1 dec1.max(inc0_prev2 1);}}// 更新全局最大值ans ans.max(inc0).max(dec0).max(inc1).max(dec1);// 更新 i-2 状态为旧的 i-1 状态即本次迭代前的 inc0/dec0inc0_prev2 next_inc0;dec0_prev2 next_dec0;}ans as i32}}---复杂度分析· 时间复杂度O(n)单次遍历。· 空间复杂度O(1)仅使用常数个变量。---测试用例可自行添加rustfn main() {let sol Solution;assert_eq!(sol.longest_alternating(vec![1, 2, 3, 4]), 2);assert_eq!(sol.longest_alternating(vec![1, 3, 2, 4]), 4); // 不删除即满足assert_eq!(sol.longest_alternating(vec![1, 2, 1, 3, 2]), 5); // 删除一个元素后可达assert_eq!(sol.longest_alternating(vec![1, 1, 1]), 1);assert_eq!(sol.longest_alternating(vec![1, 2]), 2);}该实现直接对应 LeetCode 的 Rust 模板可直接提交使用。如需进一步解释欢迎追问

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

相关推荐

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

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

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

更多资讯

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

Atlas 300V 24G上部署YOLO：模型转换与推理调优实战

链表从入门到精通：单链表操作、逆序与面试考点全解析

Servlet+JSP手写登录注册：从环境搭建到Session会话管理

从推理到构建：腾讯云ES如何让企业Agent从「能用」走向「好用」

PL/SQL Developer免Oracle客户端实战配置指南

今日更新

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

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

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

本周精选

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

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

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

本月热门

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

分布式服务的决策记录

创业产品的首版范围

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