针对 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。

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐