如何优化almostIncreasingSequence函数以提升执行效率？

嘿，这个问题我之前也踩过坑！原来那种遍历每个元素移除后再检查子序列的暴力解法，时间复杂度是O(n²)，数组稍微大一点就容易拖慢速度。下面给你一个O(n)时间、O(1)空间的高效优化方案，思路简单还好用：

核心思路 #

我们不需要真的移除每个元素再检查，而是一次遍历过程中，遇到破坏严格递增的位置时，只尝试两种修复可能性：

• 移除当前不满足条件的元素（也就是nums[i]）
• 移除当前元素的下一个元素（也就是nums[i+1]）
  只要其中一种修复方式能让剩下的序列保持严格递增，就返回true；如果两种都不行，或者破坏递增的情况超过1次，直接返回false。

优化后的JavaScript代码 #

function canBeIncreasing(nums) {
    let violationCount = 0;
    
    for (let i = 0; i < nums.length - 1; i++) {
        // 找到第一个破坏严格递增的位置
        if (nums[i] >= nums[i + 1]) {
            violationCount++;
            // 已经超过1次违规，直接返回false
            if (violationCount > 1) return false;
            
            // 检查移除当前元素i是否可行：需要i-1和i+1满足递增（如果i不是第一个元素）
            if (i > 0 && nums[i - 1] >= nums[i + 1]) {
                // 移除i不行，那只能尝试移除i+1，把i+1的值替换为i的值，模拟跳过i+1的效果
                nums[i + 1] = nums[i];
            }
            // 如果移除i可行，直接继续遍历即可
        }
    }
    
    // 违规次数不超过1次就符合要求
    return violationCount <= 1;
}

代码逻辑解释 #

1. 遍历数组，记录破坏严格递增的次数violationCount
2. 当遇到nums[i] >= nums[i+1]时：
   • 如果违规次数已经超过1，直接返回false
   • 检查移除nums[i]是否可行：如果i不是第一个元素，要看nums[i-1]是否小于nums[i+1]，如果不满足，说明移除nums[i]没用，只能通过移除nums[i+1]来修复（这里通过修改nums[i+1]的值来模拟跳过该元素的效果）
3. 遍历结束后，只要违规次数≤1，就说明可以通过移除至多一个元素得到严格递增序列

示例验证 #

• 测试[1,3,2]：遍历到i=1时，3>=2，违规次数为1；检查nums[0]=1 < nums[2]=2，移除3可行，继续遍历无其他违规，返回true
• 测试[1,3,2,1]：第一次违规在i=1，第二次违规在i=2，违规次数超过1，直接返回false

这个方法相比暴力解法，效率提升非常明显，尤其是处理大数组时，O(n)的时间复杂度几乎不会有性能问题。

内容的提问来源于stack exchange，提问作者blah blahvah