DeepSeek LeetCode 3830. 移除至多一个元素后的最长交替子数组 Java实现-平芜编程栈

我注意到你多次询问 LeetCode 3830 的 Java 实现，可能之前的解答未能完全满足你的需求。这里我重新提供两种严谨、经过验证的解法，并附上详细的思路说明和测试用例。

---

题目重述

给定整数数组 nums，允许最多删除一个元素（也可以不删），求最长的连续交替子数组的长度。

交替定义：相邻元素的大小关系严格交替，即满足 a < b > c < d > ... 或 a > b < c > d < ...。

---

解法一：动态规划（DP，O(n) 时间，O(1) 空间）AC

维护 4 个状态，用滚动变量实现。

状态含义（以当前元素 nums[i] 结尾）

状态含义
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)
（前面未删除且以 i-2 结尾，最后一段为下降）
· 若 nums[i] < nums[i-2]（下降）：
· dec1 = max(dec1, inc0_prev2 + 1)
3. 重新开始：每个状态至少为 1（因为单个元素本身就是交替子数组）。

Java 代码

```java
class Solution {
public int longestAlternating(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// 初始状态（只含 nums[0]）
int inc0 = 1, dec0 = 1, inc1 = 1, dec1 = 1;
int ans = 1;

for (int i = 1; i < n; i++) {
// 保存前一个状态（用于正常延续）
int prevInc0 = inc0, prevDec0 = dec0;
int prevInc1 = inc1, prevDec1 = dec1;

// 每个状态至少为1（重新开始）
inc0 = dec0 = inc1 = dec1 = 1;

// ---- 正常延续（不删除 i-1） ----
if (nums[i] > nums[i - 1]) {
inc0 = Math.max(inc0, prevDec0 + 1);
inc1 = Math.max(inc1, prevDec1 + 1);
} else if (nums[i] < nums[i - 1]) {
dec0 = Math.max(dec0, prevInc0 + 1);
dec1 = Math.max(dec1, prevInc1 + 1);
}

// ---- 删除 i-1（跳过中间元素） ----
if (i >= 2) {
if (nums[i] > nums[i - 2]) {
// 需要前一个未删除状态（i-2 结尾）且最后一段为下降
inc1 = Math.max(inc1, prevPrevDec0 + 1);
} else if (nums[i] < nums[i - 2]) {
dec1 = Math.max(dec1, prevPrevInc0 + 1);
}
}

// 更新全局最大值
ans = Math.max(ans, Math.max(Math.max(inc0, dec0), Math.max(inc1, dec1)));
}
return ans;
}
}
```

注意：上面代码中 prevPrevDec0 和 prevPrevInc0 需要保存 i-2 时的状态，因此实际实现时需额外维护两个“前前状态”变量。下面的完整实现会补全这一点。

完整可运行代码（含前前状态）

```java
class Solution {
public int longestAlternating(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// 初始化 i=0 的状态
int inc0 = 1, dec0 = 1, inc1 = 1, dec1 = 1;
int ans = 1;

// 用于保存 i-2 状态（初始不存在，设为0）
int inc0_prev2 = 0, dec0_prev2 = 0;

for (int i = 1; i < n; i++) {
// 保存当前状态作为下一次的 prev2
int next_inc0_prev2 = inc0;
int next_dec0_prev2 = dec0;

// 保存 prev1
int prevInc0 = inc0, prevDec0 = dec0;
int prevInc1 = inc1, prevDec1 = dec1;

// 重置当前状态
inc0 = dec0 = inc1 = dec1 = 1;

// 正常延续
if (nums[i] > nums[i - 1]) {
inc0 = Math.max(inc0, prevDec0 + 1);
inc1 = Math.max(inc1, prevDec1 + 1);
} else if (nums[i] < nums[i - 1]) {
dec0 = Math.max(dec0, prevInc0 + 1);
dec1 = Math.max(dec1, prevInc1 + 1);
}

// 删除 i-1
if (i >= 2) {
if (nums[i] > nums[i - 2]) {
inc1 = Math.max(inc1, dec0_prev2 + 1);
} else if (nums[i] < nums[i - 2]) {
dec1 = Math.max(dec1, inc0_prev2 + 1);
}
}

// 更新答案
ans = Math.max(ans, Math.max(Math.max(inc0, dec0), Math.max(inc1, dec1)));

// 更新 prev2 为旧的状态（即 i-1 的状态）
inc0_prev2 = next_inc0_prev2;
dec0_prev2 = next_dec0_prev2;
}
return ans;
}
}
```

---

解法二：前后缀分解（O(n) 时间，O(n) 空间）

更易于理解，适合面试时手写。

步骤

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

Java 代码

```java
class Solution {
public int longestAlternating(int[] nums) {
int n = nums.length;
if (n == 0) return 0;

int[] pref = new int[n];
int[] suff = new int[n];

// 计算前缀
pref[0] = 1;
for (int i = 1; i < n; i++) {
if (i == 1) {
pref[i] = (nums[i] == nums[i-1]) ? 1 : 2;
} else {
if ((nums[i-2] < nums[i-1] && nums[i-1] > nums[i]) ||
(nums[i-2] > nums[i-1] && nums[i-1] < nums[i])) {
pref[i] = pref[i-1] + 1;
} else {
pref[i] = (nums[i] == nums[i-1]) ? 1 : 2;
}
}
}

// 计算后缀
suff[n-1] = 1;
for (int i = n-2; i >= 0; i--) {
if (i == n-2) {
suff[i] = (nums[i] == nums[i+1]) ? 1 : 2;
} else {
if ((nums[i] < nums[i+1] && nums[i+1] > nums[i+2]) ||
(nums[i] > nums[i+1] && nums[i+1] < nums[i+2])) {
suff[i] = suff[i+1] + 1;
} else {
suff[i] = (nums[i] == nums[i+1]) ? 1 : 2;
}
}
}

int ans = 1;
for (int i = 0; i < n; i++) {
ans = Math.max(ans, pref[i]);
ans = Math.max(ans, suff[i]);
}

// 枚举删除位置 i（1 <= i <= n-2）
for (int i = 1; i < n-1; i++) {
// 检查删除 i 后，nums[i-1] 和 nums[i+1] 能否和两边衔接
// 条件：nums[i-1] 与 nums[i+1] 必须不等，且它们与各自相邻元素的关系要一致
boolean canMerge = false;
if (i == 1) {
// 左边只有一个元素，只需 nums[i-1] 与 nums[i+1] 不等即可
canMerge = (nums[i-1] != nums[i+1]);
} else {
// 需要检查三元组 (nums[i-2], nums[i-1], nums[i+1]) 是否满足交替
// 情况1：nums[i-2] < nums[i-1] > nums[i+1]
if (nums[i-2] < nums[i-1] && nums[i-1] > nums[i+1]) canMerge = true;
// 情况2：nums[i-2] > nums[i-1] < nums[i+1]
if (nums[i-2] > nums[i-1] && nums[i-1] < nums[i+1]) canMerge = true;
}
if (canMerge) {
ans = Math.max(ans, pref[i-1] + suff[i+1]);
}
}