如何实现数组表示整数的加一操作？（LeetCode 66）

简化版

Plus One 要处理的是“用数组表示的非负整数加 1”。核心从最低位，也就是数组末尾开始加：如果当前位小于 9，直接加 1 返回；如果当前位是 9，就变成 0，继续向前进位。若所有位都是 9，例如 [9,9,9]，最终需要新建长度多 1 的数组，首位为 1，得到 [1,0,0,0]。

时间复杂度是 O(n)，最坏情况要扫完整个数组；空间复杂度通常是 O(1)，只有全 9 时需要 O(n) 新数组。

详细版

推荐从右往左模拟手算加法：

int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }

    int[] ans = new int[digits.length + 1];
    ans[0] = 1;
    return ans;
}

关键点：

从末位开始，因为加 1 只会影响低位及连续的 9。
遇到非 9 位，给它加 1 后进位结束，可以立即返回。
遇到 9，要把它置 0，并把进位交给前一位。
全部都是 9 时，原数组所有位会被置 0，需要扩容并把最高位设为 1。

完整版教学

一、题目本质：十进制竖式加法

这道题看起来简单，但它非常适合考察候选人是否真正理解“进位”和边界。输入 [1,2,9] 表示数字 129，加一后是 130，对应数组 [1,3,0]。注意题目给的是数组，不是整数，所以不要先把数组转成 int 或 long，否则位数一长就会溢出。

手算加法的规则只有一条：从最低位开始，如果 当前位 + 进位 < 10，当前位更新后结束；如果等于 10，就写 0，把进位继续往高位传。

二、为什么从右往左

数组最右侧是个位，只有个位会直接被加 1。更高位是否变化，完全取决于低位是否连续产生进位。因此从右往左是自然方向。

输入: [1, 2, 9]
          ^
个位 9 + 1 = 10，当前位置写 0，向前进位

输入: [1, 2, 0]
       ^
十位 2 + 1 = 3，进位结束

输出: [1, 3, 0]

如果从左往右，就无法提前知道右侧是否会产生进位，反而需要额外记录状态或二次扫描。

三、核心代码如何维持不变式

从后往前遍历时，可以维护这个不变式：i 右侧的所有位已经是加一后的正确结果；如果还没返回，说明进位仍然存在，必须继续处理 i。

for (int i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
        digits[i]++;
        return digits;
    }
    digits[i] = 0;
}

当 digits[i] < 9，加 1 不会再产生进位，所以右侧已经处理完，当前位也正确，整个数组可以返回。当 digits[i] == 9，当前位加 1 后变 0，进位继续存在，所以循环继续向左。

四、全 9 情况为什么要扩容

[9] 加一是 [1,0]，[9,9] 加一是 [1,0,0]。这些结果长度都比原数组多 1，原地修改无法表示最高位新增的 1。

[9, 9, 9]
 9 + 1 -> 0, carry=1
 9 + 1 -> 0, carry=1
 9 + 1 -> 0, carry=1
最高位外仍有 carry=1
=> [1, 0, 0, 0]

面试里不要只说“全 9 特判”。更好的表达是：循环结束仍未返回，等价于所有位都把进位继续向左传递，因此需要新增最高位。

五、复杂度和空间讨论

场景	扫描位数	是否新建数组	例子
末位不是 9	1	否	`[1,2,3] -> [1,2,4]`
末尾有连续 9	连续 9 个数 + 1	否	`[1,2,9,9] -> [1,3,0,0]`
全部都是 9	n	是	`[9,9] -> [1,0,0]`

最坏情况下要处理所有位，所以时间复杂度是 O(n)。除全 9 外原地返回，额外空间 O(1)；全 9 需要新数组，返回值空间 O(n)。

六、为什么不要转整数

把 [9,9,9,...] 转成整数再加一，看起来省事，但会遇到三个问题：第一，数组长度可能远超 64 位整数范围；第二，语言的整数溢出会让结果错误；第三，题目本来就是考察按位模拟，不是考察大整数库。

如果面试官追问“能不能用 BigInteger”，可以回答：工程里可以，但算法题不建议，因为它绕开了进位逻辑，也不满足面试希望你展示的核心能力。

七、面试现场如何验证

验证这道题时至少覆盖四类输入：

普通无进位：[1,2,3] -> [1,2,4]
单位进位：[1,2,9] -> [1,3,0]
多位连续进位：[1,9,9] -> [2,0,0]
全 9 扩容：[9,9,9] -> [1,0,0,0]

这些样例能覆盖“立即返回”“继续进位”“新建数组”三条路径。

八、常见误区与追问

误区：先把数组转成整数再加一。 大位数会溢出，也绕过了题目考点。
误区：遇到 9 只置 0，不继续向前进位。 [1,9,9] 会被算错。
误区：全 9 时返回原数组。 原数组长度不够，必须新增最高位。
误区：从左往右处理更直观。 加一的影响从个位开始，从左往右会失去进位方向。
追问：为什么遇到非 9 可以立即返回？ 因为当前位加 1 后不会再产生进位，左侧高位不会受影响。
追问：空间复杂度到底是 O(1) 还是 O(n)？ 原地分支是 O(1)，全 9 返回新数组时需要 O(n) 返回空间。

九、加强记忆

这题本质是十进制竖式加法，不要转整数。
从右往左扫，遇到非 9 加一后立即返回。
遇到 9 就置 0，把进位继续交给前一位。
循环结束还没返回，说明全是 9，新建数组并设 ans[0]=1。
复杂度记为最坏 O(n)，边界重点看 [9] 和 [9,9,9]。

简化版

详细版