当前位置：首页 > news >正文

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

news 2026/8/8 9:02:23

针对 LeetCode 3830“移除至多一个元素后的最长交替子数组”，这里提供两种 Python3 解法：动态规划 (O(n) 时间, O(1) 空间) 和前后缀分解 (O(n) 时间, O(n) 空间)。

---

解法一：动态规划（推荐）

维护 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（重新开始）。

Python 代码

```python
class Solution:
def longestAlternating(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0

# 初始化 i=0 的状态
inc0 = dec0 = inc1 = dec1 = 1
ans = 1

# 用于保存 i-2 状态的变量（初始不存在，设为0）
inc0_prev2 = dec0_prev2 = 0

for i in range(1, n):
# 保存当前状态作为下一次的 prev2
next_inc0_prev2 = inc0
next_dec0_prev2 = dec0

# 保存 prev1
prev_inc0, prev_dec0 = inc0, dec0
prev_inc1, prev_dec1 = inc1, dec1

# 重置当前状态（每个状态至少为1）
inc0 = dec0 = inc1 = dec1 = 1

# 正常延续（不删除 i-1）
if 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_prev2
dec0_prev2 = next_dec0_prev2

return ans
```

---

解法二：前后缀分解（更直观）

步骤

1. 前缀数组 pref[i]：以 i 结尾的最长交替子数组长度（不删除）。
2. 后缀数组 suff[i]：以 i 开头的最长交替子数组长度（不删除）。
3. 答案候选：
· 不删除：max(pref[i])
· 删除位置 i（1 <= i <= n-2）：若能合并，尝试 pref[i-1] + suff[i+1]

Python 代码

```python
class Solution:
def longestAlternating(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0

# 计算前缀
pref = [1] * n
for i in range(1, n):
if i == 1:
pref[i] = 2 if nums[i] != nums[i-1] else 1
else:
# 检查 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] + 1
else:
pref[i] = 2 if nums[i] != nums[i-1] else 1

# 计算后缀
suff = [1] * n
for i in range(n-2, -1, -1):
if i == n-2:
suff[i] = 2 if nums[i] != nums[i+1] else 1
else:
if (nums[i] < nums[i+1] > nums[i+2]) or (nums[i] > nums[i+1] < nums[i+2]):
suff[i] = suff[i+1] + 1
else:
suff[i] = 2 if nums[i] != nums[i+1] else 1

ans = max(pref + suff) # 不删除的情况

# 枚举删除位置 i（1 <= i <= n-2）
for i in range(1, n-1):
can_merge = False
if i == 1:
# 左边只有一个元素，只需 nums[i-1] 和 nums[i+1] 不等
can_merge = (nums[i-1] != nums[i+1])
else:
# 检查三元组 (nums[i-2], nums[i-1], nums[i+1]) 是否满足交替
# 可能模式: nums[i-2] < nums[i-1] > nums[i+1]
# 或 nums[i-2] > nums[i-1] < nums[i+1]
if (nums[i-2] < nums[i-1] and nums[i-1] > nums[i+1]) or \
(nums[i-2] > nums[i-1] and nums[i-1] < nums[i+1]):
can_merge = True
if can_merge:
ans = max(ans, pref[i-1] + suff[i+1])

return ans
```