LeetCode 'Plus One'递归解法超时问题排查与优化求助

题目描述 #

给定一个以整数数组digits形式表示的非负大整数，digits[i]是该整数的第i位数字，数字从左到右按最高位到最低位排列，且整数无前导零。将该大整数加1后，返回结果数字数组。

示例 #

示例1 #

输入：digits = [1,2,3]
输出：[1,2,4]
解释：数组表示整数123，加1后得到124，故返回[1,2,4]。

示例2 #

输入：digits = [9]
输出：[1,0]
解释：数组表示整数9，加1后得到10，故返回[1,0]。

约束条件 #

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits无前导零

我的解法 #

// [9] 会变成 [1,0]
var plusOne = function(digits) {
    let len = digits.length;
    // 从数组末尾往前遍历
    for(let i = len-1; i >= 0; i--) {
        // 如果当前位是9，就把它置0（第14行）
        // 同时通过递归检查前一位是否也是9（第19行）
        // 如果当前位不是9，就把它加1然后返回digits（第22、23行）
        // 如果没有前一位了，就在数组开头加1然后返回digits（第16、17行）
        if(digits[i] == 9) {
            digits[i] = 0;
            if(!digits[i - 1]){
                digits.unshift(1);
                return digits;
            } else {
                plusOne(digits.slice(0, i-1));
            }
        } else {
            digits[i] = digits[i] + 1;
            return digits;
        }
    }
};

let array = [9,9,9];

console.log(plusOne(array));

// 这段代码在输入以下数组时会出错：
// [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]

遇到的问题 #

这个问题的难点在于处理连续的9，因为加1会导致连续进位到更高位。我用递归的方式解决，大部分测试用例都能通过，但输入全是9的长数组时，LeetCode提示**超时（Time limit exceeded）**错误。

求助问题 #

这是不是栈大小导致的问题？有没有办法优化上述代码的空间复杂度？我刚接触递归，不知道怎么降低时间/空间复杂度。

解答 #

问题原因分析 #

你的递归写法确实会引发超时问题，核心原因有两个：

1. 不必要的数组副本开销：每次递归调用plusOne(digits.slice(0, i-1))时，slice会生成新的数组副本，对于长度100的全9数组，会生成近50个不同长度的数组，内存分配和复制操作会大幅增加时间消耗。
2. 无效递归调用：递归调用后没有用返回值更新原数组，相当于做了无用功，进一步浪费计算资源。
   栈深度（最多100层）本身不会直接导致溢出，但叠加上述开销后就触发了超时。

优化方案：迭代写法（O(n)时间 + O(1)空间） #

递归完全没必要，用迭代从后往前遍历就能高效解决，且无需额外创建数组副本：

var plusOne = function(digits) {
    const n = digits.length;
    // 从最后一位开始遍历处理进位
    for (let i = n - 1; i >= 0; i--) {
        if (digits[i] !== 9) {
            digits[i] += 1;
            return digits;
        }
        // 当前位是9，置0后继续往前处理进位
        digits[i] = 0;
    }
    // 所有位都是9，循环结束后在数组开头加1
    digits.unshift(1);
    return digits;
};

优化点说明 #

• 时间复杂度：O(n)，最多遍历整个数组一次。
• 空间复杂度：O(1)（仅全9情况需要在数组开头加1，这是结果存储的必要开销，不属于额外空间消耗）。
• 彻底避免了递归栈开销和数组切片的冗余计算，效率远高于递归写法。

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