题目描述

给定一个表示大整数的整数数组 digits，其中 digits[i]是整数的第 i位数字。这些数字按从左到右的顺序排列（从最高位到最低位）。这个大整数不包含任何前导 0。请将大整数加 1，并返回结果的数字数组。

示例：

• 示例 1： 输入：digits = [1,2,3] 输出：[1,2,4] 解释：123 + 1 = 124。
• 示例 2： 输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：4321 + 1 = 4322。
• 示例 3： 输入：digits = [9] 输出：[1,0] 解释：9 + 1 = 10。

约束条件：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits不包含任何前导 0。

---

解题思路

题目要求模拟大整数加 1 的过程。由于大整数可能非常大（数组长度可达 100），因此不能直接转换为整数类型计算（可能导致溢出）。需要逐位处理加 1 操作，并正确处理进位。以下是具体步骤：

1. 从最低位开始加 1： 从数组末尾（最低位）开始遍历，将当前位加 1。
2. 处理进位： 如果加 1 后当前位小于 10，则直接返回结果数组（无进位）。 如果加 1 后当前位等于 10，则将当前位置为 0，并继续向高位进位（即高位需要再加 1）。
3. 处理最高位进位： 如果遍历完整个数组后仍有进位（即最高位进位），则需要创建一个新数组，长度为原数组长度加 1。新数组的首位为 1，其余位为 0（因为进位后所有低位都变成了 0）。

示例分析：

• 输入 [9,9,9]： 最低位 9 + 1 = 10→ 置为 0，进位 1。 中间位 9 + 1 = 10→ 置为 0，进位 1。 最高位 9 + 1 = 10→ 置为 0，进位 1。 最终结果需新建数组 [1,0,0,0]。

---

代码实现

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            digits[i]++; // 当前位加 1
            if (digits[i] < 10) {
                return digits; // 无进位，直接返回
            }
            digits[i] = 0; // 进位后当前位置 0
        }
        // 处理最高位进位（如 999 -> 1000）
        int[] newDigits = new int[n + 1];
        newDigits[0] = 1; // 首位为 1，其余位为 0
        return newDigits;
    }
}

---

复杂度分析

• 时间复杂度： O(n)，其中 n是数组长度。最坏情况下需要遍历整个数组（如 [9,9,...,9]）。
• 空间复杂度： O(1)（不考虑输出数组）。最坏情况下（最高位进位）需要额外 O(n)空间存储新数组。