針對 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 模板可直接提交使用。如需進一步解釋歡迎追問