加1加1加1
在日常开发或算法面试中，经常会遇到 “数字加一” 的场景 —— 但这里的数字并非简单的整数，而是用数组表示的（例如 [1,2,3] 代表 123）。这种场景看似简单，却暗藏边界陷阱，今天我们就来彻底拆解这个问题，从思路到代码一步步搞定。
一、问题描述
题目要求
给定一个非负整数，以数组 digits 的形式呈现（数组中每个元素是单个数字，且不包含前导 0），对其执行 “加一” 操作，返回加一后的数组结果。
示例说明
输入 | 输出 | 说明 |
[1,2,3] | [1,2,4] | 123 + 1 = 124 |
[9,9,9] | [1,0,0,0] | 999 + 1 = 1000（数组扩容） |
[1,9,9] | [2,0,0] | 199 + 1 = 200（进位传递） |
[0] | [1] | 0 + 1 = 1（单个元素边界） |
二、核心思路分析
1. 为什么从后向前遍历？
加一操作的本质是 “从最低位开始计算”，而数组的最后一个元素恰好对应数字的最低位（例如 [1,2,3] 中 3 是个位）。因此，从数组末尾向前遍历是最符合直觉的选择。
2. 进位处理的关键逻辑
- 若当前位数字 不是 9：直接加 1，此时无后续进位，直接返回结果（因为低位已处理完毕）。
- 若当前位数字 是 9：加 1 后会变成 0，且需要向高位进位，因此继续向前遍历处理下一位。
3. 全 9 场景的边界处理
如果遍历完所有元素都没有返回（说明数组中所有数字都是 9），此时需要创建一个新数组：首位为 1，后面拼接原数组（原数组已全部变为 0），例如 [9,9,9] → [1] + [0,0,0] = [1,0,0,0]。
三、Python 完整代码实现（含注释）
py取消自动换行复制
四、代码深度解析
1. 遍历逻辑拆解
py取消自动换行复制
- len(digits)-1：数组最后一个元素的索引（最低位）。
- -1：遍历终止条件（不包含 -1，即遍历到索引 0）。
- -1：步长为 -1，实现从后向前遍历。
2. 进位处理细节
以 [1,9,9] 为例：
- 遍历索引 2（数字 9）：置为 0，继续向前。
- 遍历索引 1（数字 9）：置为 0，继续向前。
- 遍历索引 0（数字 1）：加 1 变为 2，返回 [2,0,0]。
3. 全 9 场景的巧妙处理
当数组全为 9 时，循环结束后 digits 已变为 [0,0,...,0]，此时 [1] + digits 直接生成首位为 1、后续为 0 的新数组，无需额外判断。
五、复杂度分析
场景 | 时间复杂度 | 空间复杂度 | 说明 |
普通场景（非全 9） | O(n) | O(1) | 原地修改数组，无额外空间 |
全 9 场景 | O(n) | O(n+1) | 新建长度为 n+1 的数组 |
- 时间复杂度：最坏情况下需遍历整个数组（如全 9 场景），因此为 O (n)（n 为数组长度）。
- 空间复杂度：普通场景下原地修改，空间复杂度为 O (1)；全 9 场景需新建数组，空间复杂度为 O (n)。
六、扩展延伸（面试高频变种）
1. 变种问题：数组实现 “加 k”（k 为任意正整数）
原问题是 “加 1”，如果改为 “加 k”（例如 [1,2,3] + 45 → [1,6,8]），该如何修改？
思路：
- 进位初始值设为 k，而非 1。
- 遍历数组时，当前位 = (原数字 + 进位) % 10，新进位 = (原数字 + 进位) // 10。
- 遍历结束后，若进位 > 0，将进位拆分为单个数字拼接到数组前面。
代码实现：
pyth取消自动换行复制
def plus_k(digits, k):
carry = k # 进位初始值为 k
for i in range(len(digits)-1, -1, -1):
total = digits[i] + carry
digits[i] = total % 10 # 当前位结果
carry = total // 10 # 新进位
if carry == 0: # 无进位时直接返回
return digits
# 处理剩余进位（如 carry=123 → [1,2,3]）
while carry > 0:
digits.insert(0, carry % 10)
carry = carry // 10
return digits
# 测试：[1,2,3] + 45 → [1,6,8]
print(plus_k([1,2,3], 45)) # 输出 [1,6,8]
# 测试：[9,9] + 3 → [1,0,2]
print(plus_k([9,9], 3)) # 输出 [1,0,2]
2. 变种问题：处理负数（数组表示负数加一）
如果数组表示负数（例如 [-1,9,9] 代表 -199），加一操作后应为 -198（数组 [-1,9,8]），该如何处理？
思路：
- 负数加一本质是 “减 1”（注意借位逻辑与加一相反）。
- 从末尾向前遍历，遇到非 0 的数字：减 1，返回结果。
- 遇到 0：变为 9，继续向前处理借位。
- 若所有位都是 0（如 [-1,0,0]），则变为 [-0,9,9] → 简化为 [-9,9]（但需注意前导 0 处理）。
七、总结
数组加一问题的核心是 “进位处理” 和 “边界场景覆盖”：
- 遍历方向：从后向前（符合数字计算逻辑）。
- 核心逻辑：非 9 直接加 1 返回，9 则置 0 进位。
- 边界处理：全 9 场景需数组扩容。