66. 加一（Plus One）

频次 ★★ · 难度 🟢 · 高频：全厂

题目

给定一个非负整数的大数表示（数组形式，最高位在索引 0），对该数加一，返回结果数组。

示例：

输入: digits = [1,2,3]
输出: [1,2,4]

输入: digits = [9]
输出: [1,0]

思路

从最低位（数组末尾）开始加一：

• 如果当前位加一后小于 10，无进位，直接返回
• 如果当前位等于 9，加一后变为 0，有进位，继续处理前一位
• 如果所有位都有进位（如 999 → 1000），需要创建新数组，长度 +1，首位为 1

代码

public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] %= 10;
        if (digits[i] != 0) {
            return digits; // 无进位，直接返回
        }
    }
    // 全部位都有进位（如 999 -> 1000）
    digits = new int[digits.length + 1];
    digits[0] = 1;
    return digits;
}

复杂度

• 时间：O(n) — 最坏情况遍历所有位（如 999…9）
• 空间：O(1) — 原地修改，新建数组仅在进位时且最多 O(n) 输出

边界条件

• 单个数字且为 9（[9]）：加一后变 0，进位到最前面，触发新建数组，结果 [1,0]。
• 全 9（如 [9,9,9]）：每一位都进位，循环走完仍未 return，触发新建数组，结果 [1,0,0,0]。
• 末位不是 9（如 [1,2,3]）：第一次循环就无进位直接 return，是最常见的快速路径。

变式

• 如果输入是字符串形式的大数而不是数组：思路完全一样（从低位往高位处理进位），只是要用 StringBuilder 而不是数组下标操作，且最后需要反转字符串。
• 如果是”加上任意一个数”而不是固定”加一”：需要维护进位变量 carry，逐位相加取模，和 2. 两数相加 的链表版本是同一套思路，只是数据结构从链表换成了数组。

易错点

• 判断”是否需要进位”不能只看是否等于 10，要用 digits[i] %= 10 之后再判断 != 0 决定要不要继续往前进位，代码里这个顺序（先加一取模，再判断）是关键。
• 全部进位触发”新建数组”分支容易漏写：如果只写了循环内的 return，[9,9,9] 这种输入会导致函数没有返回值（编译错误）或错误地返回未处理的原数组。

面试追问

• 为什么不直接把数组转成整数算术运算再转回来？ 大数可能超出 long 甚至 BigInteger 的常规使用场景（题目本意是练习”逐位处理进位”这个技巧），而且数字位数很多时转换成整数本身就会溢出，逐位模拟是通用且不受长度限制的方法。
• 除了从末位开始逐位处理，还有别的角度吗？ 可以换个角度想：只有当末尾连续的 9 会变成 0，第一个非 9 的位置加一后循环结束；如果整个数组全是 9，则长度整体 +1、其余位全为 0，这也是一种等价但更”一步到位”的实现方式。

关联题

• 同套路：2. 两数相加 —— 链表版进位模拟；415. 字符串相加 —— 字符串版
• 知识点：低位起 + carry 变量 + 全 9 时扩容补 1，进位模拟的最小完整样例