[066] 加一 (Plus One)

难度：简单 | 标签：数组、数学

题目描述

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

请将该大整数加 1，并返回结果的数字数组。

示例 1：

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

示例 2：

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

解法：倒序遍历 (Reverse Iteration) —— 推荐 ✅

我们需要模拟手工加法的过程，从个位（数组末尾）开始向前处理进位。

1. 从后往前遍历数组。
2. 情况 A：当前位不是 9。
   • 直接将该位 +1，然后直接返回结果。因为没有进位了，前面的数字不需要变。
3. 情况 B：当前位是 9。
   • 将该位变为 0，继续循环处理前一位（相当于进位 1）。
4. 特殊情况：跑完了循环没返回（例如 999）。
   • 说明所有位都是 9，现在全变成了 0。
   • 需要增加一位，首位为 1，其余为 0（如 1000）。

代码实现 (C++)

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        
        // 1. 从个位开始倒序遍历
        for(int i = n - 1; i >= 0; i--) {
            // 如果不是 9，直接加 1 返回，结束战斗
            if(digits[i] != 9) {
                digits[i]++;
                return digits;
            } 
            // 如果是 9，变成 0，继续循环处理前一位
            else {
                digits[i] = 0;
            }
        }

        // 2. 处理全是 9 的情况 (e.g. 99 -> 100)
        // 此时 digits 已经全为 0 了，需要增加一位长度
        vector<int> res(n + 1); // 默认初始化全为 0
        res[0] = 1;             // 首位设为 1
        return res;
    }
};

复杂度分析

• 时间复杂度：

  最坏情况（如 999）需要遍历整个数组。

• 空间复杂度：

  大部分情况原地修改。特殊情况（全 9）需要 的空间来存储新数组。

易错点分析

1. 进位处理：

   很多人会想着用一个 carry 变量来记录进位，虽然逻辑没错，但不如“遇 9 变 0，非 9 加 1 返回”这种贪心策略简洁。

2. 全 9 溢出：

   容易忘记处理 [9, 9, 9] 这种情况。循环结束后如果不返回，说明需要进位到最高位的前面。直接创建一个 n+1 的数组且首位为 1 是最快的写法。