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

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

news 2026/8/8 8:46:48

针对 LeetCode 3830“移除至多一个元素后的最长交替子数组”，这里提供 JavaScript (ES6+) 实现，采用动态规划 (O(n) 时间, O(1) 空间)，代码简洁高效。

---

核心思路

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

---

JavaScript 代码

```javascript
/**
* @param {number[]} nums
* @return {number}
*/
var longestAlternating = function(nums) {
const n = nums.length;
if (n === 0) return 0;

// 初始化状态（以 nums[0] 结尾）
let inc0 = 1, dec0 = 1, inc1 = 1, dec1 = 1;
let ans = 1;

// 保存 i-2 时的未删除状态（初始不存在，设为 0）
let inc0_prev2 = 0, dec0_prev2 = 0;

for (let i = 1; i < n; i++) {
// 保存当前状态，作为下一轮迭代的 i-2
const next_inc0 = inc0, next_dec0 = dec0;

// 保存上一轮状态（i-1）
const prev_inc0 = inc0, prev_dec0 = dec0;
const prev_inc1 = inc1, prev_dec1 = dec1;

// 重置当前状态（至少为 1）
inc0 = dec0 = inc1 = dec1 = 1;

// ---- 正常延续（不删除 i-1） ----
if (nums[i] > nums[i - 1]) {
inc0 = Math.max(inc0, prev_dec0 + 1);
inc1 = Math.max(inc1, prev_dec1 + 1);
} else if (nums[i] < nums[i - 1]) {
dec0 = Math.max(dec0, prev_inc0 + 1);
dec1 = Math.max(dec1, prev_inc1 + 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, inc0, dec0, inc1, dec1);

// 更新 i-2 状态为旧的 i-1 状态（即本次迭代前的 inc0/dec0）
inc0_prev2 = next_inc0;
dec0_prev2 = next_dec0;
}

return ans;
};
```

---

复杂度分析

· 时间复杂度：O(n)，单次遍历。
· 空间复杂度：O(1)，仅使用常数个变量。

---

测试用例

```javascript
console.log(longestAlternating([1,2,3,4])); // 2
console.log(longestAlternating([1,3,2,4])); // 4
console.log(longestAlternating([1,2,1,3,2])); // 5
console.log(longestAlternating([1,1,1])); // 1
console.log(longestAlternating([1,2])); // 2
```

---

如果需要更直观的解法，也可以使用前后缀分解，但 DP 解法空间更优。以上代码可直接提交到 LeetCode。

查看全文

http://www.jsqmd.com/news/1351714/