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

针对 LeetCode 3830“移除至多一个元素后的最长交替子数组”，这里提供 Rust 实现，采用 动态规划 (O(n) 时间, O(1) 空间)，代码高效且安全。

---

核心思路

维护 4 个状态（以当前元素结尾）：

· inc0：最后一段比较为 上升 (<)，未删除元素
· dec0：最后一段比较为 下降 (>)，未删除元素
· inc1：最后一段比较为 上升，已删除一个元素
· dec1：最后一段比较为 下降，已删除一个元素

每个状态初始为 1（仅包含当前元素本身）。

转移（遍历 i 从 1 到 n-1）：

1. 正常延续（不删除 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 + 1
2. 删除 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 代码实现

```rust
impl Solution {
pub fn longest_alternating(nums: Vec<i32>) -> 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 时的未删除状态（初始不存在，设为 0）
let (mut inc0_prev2, mut dec0_prev2) = (0, 0);

for i in 1..n {
// 保存当前状态，作为下一轮迭代的 prev2
let (next_inc0, next_dec0) = (inc0, dec0);

// 保存上一轮状态（prev1）
let (prev_inc0, prev_dec0) = (inc0, dec0);
let (prev_inc1, prev_dec1) = (inc1, dec1);

// 重置当前状态（至少为 1）
inc0 = 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/dec0）
inc0_prev2 = next_inc0;
dec0_prev2 = next_dec0;
}

ans as i32
}
}
```

---

复杂度分析

· 时间复杂度：O(n)，单次遍历。
· 空间复杂度：O(1)，仅使用常数个变量。

---

测试用例（可自行添加）

```rust
fn 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 模板，可直接提交使用。如需进一步解释，欢迎追问！