题目描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：

输入：digits = [0]
输出：[1]

解题

解法一： 逆序遍历并逐位处理进位

思路

初始化进位标志：定义变量 carry 并赋值为 1

逆序遍历数组：加一操作可能导致低位向高位的进位，从低位开始处理有利于逐步解决进位问题。

逐位加一并处理进位： 计算当前位的新值：将当前数字 digits[i] 与进位值 carry 相加，得到临时变量 temp。然后将 temp 除以 10 的余数赋值给当前数字，然后更新进位值 carry。记录当前位加一后可能产生的进位值，供下一次迭代使用。 最后检查 carry 是否为 0。若为 0，说明没有更高位需要进位，此时终止循环。

遍历结束后，检查 carry 的值。如果大于 0，说明最高位也发生了进位。此时在数组最前面插入一个新的元素，其值为 carry。

算法复杂度

时间复杂度：O(⁡n)，其中 n为数组的长度。

---

空间复杂度：O(1)。

代码

python">class Solution:def plusOne(self, digits: List[int]) -> List[int]:# 从数组末尾开始遍历carry = 1  # 初始化进位标志for i in range(len(digits) - 1, -1, -1):# 尝试加一并处理进位temp = digits[i] + carrydigits[i] = temp % 10  # 更新当前位的值carry = temp // 10  # 计算新的进位值if carry == 0:  # 如果没有进位，结束循环break# 如果最高位也发生了进位，需要在数组前添加一个新元素if carry > 0:digits.insert(0, carry)return digits