針對(duì) LeetCode 3830“移除至多一個(gè)元素后的最長交替子數(shù)組”這里提供兩種 Python3 解法動(dòng)態(tài)規(guī)劃 (O(n) 時(shí)間, O(1) 空間) 和前后綴分解 (O(n) 時(shí)間, O(n) 空間)。---解法一動(dòng)態(tài)規(guī)劃推薦維護(hù) 4 個(gè)狀態(tài)用滾動(dòng)變量實(shí)現(xiàn)無需數(shù)組。狀態(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 1· inc1 dec1_prev 1· 若 nums[i] nums[i-1]下降· dec0 inc0_prev 1· dec1 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重新開始。Python 代碼pythonclass Solution:def longestAlternating(self, nums: List[int]) - int:n len(nums)if n 0:return 0# 初始化 i0 的狀態(tài)inc0 dec0 inc1 dec1 1ans 1# 用于保存 i-2 狀態(tài)的變量初始不存在設(shè)為0inc0_prev2 dec0_prev2 0for i in range(1, n):# 保存當(dāng)前狀態(tài)作為下一次的 prev2next_inc0_prev2 inc0next_dec0_prev2 dec0# 保存 prev1prev_inc0, prev_dec0 inc0, dec0prev_inc1, prev_dec1 inc1, dec1# 重置當(dāng)前狀態(tài)每個(gè)狀態(tài)至少為1inc0 dec0 inc1 dec1 1# 正常延續(xù)不刪除 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 為舊的狀態(tài)即 i-1 的狀態(tài)inc0_prev2 next_inc0_prev2dec0_prev2 next_dec0_prev2return ans---解法二前后綴分解更直觀步驟1. 前綴數(shù)組 pref[i]以 i 結(jié)尾的最長交替子數(shù)組長度不刪除。2. 后綴數(shù)組 suff[i]以 i 開頭的最長交替子數(shù)組長度不刪除。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# 計(jì)算前綴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# 計(jì)算后綴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:# 左邊只有一個(gè)元素只需 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---兩種解法對(duì)比特性 DP 解法 前后綴分解時(shí)間復(fù)雜度 O(n) O(n)空間復(fù)雜度 O(1) O(n)代碼復(fù)雜度 狀態(tài)多需仔細(xì) 邏輯清晰適用場景 內(nèi)存受限 面試/日常優(yōu)先建議競賽或內(nèi)存敏感場景用 DP面試或需要快速實(shí)現(xiàn)用前后綴分解。如有任何疑問歡迎繼續(xù)交流