分析

• 本题的考点：高精度加法。

• 直接使用加法的规则模拟一遍即可，因为加上的是1，因此最终的结果最多比digit多一位，比如99+1=100，因此使用原数组记录结果即可。

• 注意个位在digits[0]这样比较方便计算，因此需要对输入进行翻转。

代码

• C++

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {

        reverse(digits.begin(), digits.end());
        int t = 1;
        for (auto &x : digits) {
            t += x;
            x = t % 10;
            t /= 10;
        }
        if (t) digits.push_back(t);
        reverse(digits.begin(), digits.end());

        return digits;
    }
};

• Java

class Solution {
    public int[] plusOne(int[] digits) {

        reverse(digits);
        int t = 1;
        for (int i = 0; i < digits.length; i++) {
            t += digits[i];
            digits[i] = t % 10;
            t /= 10;
        }
        if (t != 0) {
            int[] res = new int[digits.length + 1];
            System.arraycopy(digits, 0, res, 0, digits.length);
            res[digits.length] = 1;
            reverse(res);
            return res;
        }
        reverse(digits);
        return digits;
    }

    private void reverse(int[] nums) {
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
        }
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为数组长度。

• 空间复杂度：$O(n)$。