針對(duì) LeetCode 3830“移除至多一個(gè)元素后的最長交替子數(shù)組”這里提供 Rust 實(shí)現(xiàn)采用 動(dòng)態(tài)規(guī)劃 (O(n) 時(shí)間, O(1) 空間)代碼高效且安全。---核心思路維護(hù) 4 個(gè)狀態(tài)以當(dāng)前元素結(jié)尾· inc0最后一段比較為 上升 ()未刪除元素· dec0最后一段比較為 下降 ()未刪除元素· inc1最后一段比較為 上升已刪除一個(gè)元素· dec1最后一段比較為 下降已刪除一個(gè)元素每個(gè)狀態(tài)初始為 1僅包含當(dāng)前元素本身。轉(zhuǎn)移遍歷 i 從 1 到 n-11. 正常延續(xù)不刪除 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使用一次刪除機(jī)會(huì)需 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. 每個(gè)狀態(tài)至少為 1重新開始。---Rust 代碼實(shí)現(xiàn)rustimpl Solution {pub fn longest_alternating(nums: Veci32) - i32 {let n nums.len();if n 0 {return 0;}if n 1 {return 1;}// 初始狀態(tài)以 nums[0] 結(jié)尾let (mut inc0, mut dec0) (1, 1);let (mut inc1, mut dec1) (1, 1);let mut ans 1;// 保存 i-2 時(shí)的未刪除狀態(tài)初始不存在設(shè)為 0let (mut inc0_prev2, mut dec0_prev2) (0, 0);for i in 1..n {// 保存當(dāng)前狀態(tài)作為下一輪迭代的 prev2let (next_inc0, next_dec0) (inc0, dec0);// 保存上一輪狀態(tài)prev1let (prev_inc0, prev_dec0) (inc0, dec0);let (prev_inc1, prev_dec1) (inc1, dec1);// 重置當(dāng)前狀態(tài)至少為 1inc0 1;dec0 1;inc1 1;dec1 1;// ---- 正常延續(xù)不刪除 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 狀態(tài)為舊的 i-1 狀態(tài)即本次迭代前的 inc0/dec0inc0_prev2 next_inc0;dec0_prev2 next_dec0;}ans as i32}}---復(fù)雜度分析· 時(shí)間復(fù)雜度O(n)單次遍歷。· 空間復(fù)雜度O(1)僅使用常數(shù)個(gè)變量。---測試用例可自行添加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); // 刪除一個(gè)元素后可達(dá)assert_eq!(sol.longest_alternating(vec![1, 1, 1]), 1);assert_eq!(sol.longest_alternating(vec![1, 2]), 2);}該實(shí)現(xiàn)直接對(duì)應(yīng) LeetCode 的 Rust 模板可直接提交使用。如需進(jìn)一步解釋歡迎追問