难度: Easy
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 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]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9运行时间: 40 ms
内存: 14.8 MB
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
digits = [0] + digits
for i in range(len(digits)-1, -1, -1):
if digits[i] != 9:
digits[i] += 1
break
else:
digits[i] = 0
if digits[0] == 0:
return digits[1:]
else:
return digits
这个题解的思路是先在数组最前面添加一个0作为进位标志，然后从数组末尾开始遍历。如果当前位不为9，直接加1然后结束遍历；如果当前位为9，则将其置为0，继续遍历前一位。最后根据最前面的进位标志是否为0，决定是否要将其去掉。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
# 在数组最前面添加一个0作为进位标志
digits = [0] + digits
# 从数组末尾开始遍历
for i in range(len(digits)-1, -1, -1):
# 如果当前位不为9，直接加1然后结束遍历
if digits[i] != 9:
digits[i] += 1
break
# 如果当前位为9，则将其置为0，继续遍历前一位
else:
digits[i] = 0
# 根据最前面的进位标志是否为0，决定是否要将其去掉
if digits[0] == 0:
return digits[1:]
else:
return digits
在数组最前面添加一个0作为进位标志的主要原因是为了简化代码处理进位的逻辑。这种方法避免了在数组的最高位产生进位时需要额外的数组扩展操作。例如，当数组中的所有数字均为9时，其结果需要在最高位前增加一个新的最高位（1），直接在数组前添加一个0可以在一次遍历中解决这个问题，如果最前面的0变为1，则保留，否则去除。这样做可以使代码更为简洁和高效。
是的，这种方法可以正确处理全部数字为9的情况。例如对于输入[9, 9, 9]，在数组前添加0后变为[0, 9, 9, 9]。从数组末尾开始遍历，每个9都会变成0并继续向前进位，最终数组变为[1, 0, 0, 0]。由于最前面的0变为1，因此不会被去除，最终正确返回[1, 0, 0, 0]。
确实，不是所有的元素都需要检查或修改。break语句的使用是为了提高算法效率，避免不必要的操作。当遍历到数组中的某一个元素并且该元素不是9时，意味着这个位置可以直接加1而不需要进位，因此后续的元素也不需要修改，这时可以直接终止循环。例如，对于输入[1, 2, 3]，加1操作仅发生在最后一个元素上变为[1, 2, 4]，遍历到3时直接将其改为4并终止循环。
对于全部都是9的数组[9, 9, 9, 9]，算法首先会在数组前添加一个0，变为[0, 9, 9, 9, 9]。然后从数组的最后一位开始遍历，每个9都会变成0，并且由于持续进位，最前面的0会变成1。所以，最终数组会从[0, 9, 9, 9, 9]变为[1, 0, 0, 0, 0]。由于最前面的0变为1，这个1是必需的，因为它代表了一个新的最高位，最终算法返回[1, 0, 0, 0, 0]。这样处理确保了算法能够有效应对所有元素为9的情况，正确地增加一个位数。