針對 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面試或需要快速實現用前后綴分解。如有任何疑問歡迎繼續交流