加一 - 题目笔记

📝 算法笔记：66. 加一 (Plus One)

1. 题目描述

给定一个由整数数组表示的非负大整数，数组每个元素存一个数字，最高位在数组首部。将该数加 1并返回结果数组。

• 输入：digits = [1, 2, 9]

• 输出：[1, 3, 0]

2. 核心思路：贪心遍历 (Greedy Approach)

这道题的核心在于处理进位。由于只加 1，进位只会发生在当前数字是9的情况下。

• 从后向前遍历数组：

  1. 如果当前位< 9：直接加 1 并返回数组（因为不会产生更高的进位）。

  2. 如果当前位== 9：将当前位设为0，继续循环处理前一位。

• 特殊情况：如果循环结束仍未返回（例如输入为[9, 9, 9]），说明产生了最高位进位。此时直接在数组最前面补一个1即可。

3. 代码实现 (Python)

Python

class Solution: def plusOne(self, digits: List[int]) -> List[int]: n = len(digits) # 1. 从低位到高位反向遍历 for i in range(n - 1, -1, -1): if digits[i] < 9: digits[i] += 1 # 找到第一个不需进位的数，加 1 return digits # 关键：直接返回结果 # 如果是 9，则该位变 0，继续循环处理前一位 digits[i] = 0 # 2. 如果循环走完还没返回，说明是 99...9 的情况 # 此时 digits 已全变成 0，只需在最前面加个 1 return [1] + digits

4. 复杂度分析

• 时间复杂度：$O(n)$

  • 最好情况：末尾不是 9，只需 $O(1)$。

  • 最坏情况：全是 9，需要遍历一遍整个数组，$O(n)$。

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

  • 如果不算返回数组的空间，我们在原数组上操作，是 $O(1)$。

  • 如果是全 9 情况，需要额外构造一个长度为 $n+1$ 的结果，空间复杂度为 $O(n)$。

5. 进阶思考：为什么这是最优解？

1. 避开了数值转换：不需要先将数组转成整数（Python 虽然支持大整数，但在其他语言如 C++ 中会溢出），直接操作数组鲁棒性更强。

2. 提前终止：一旦遇到不需要进位的位，立即return，避免了无效的遍历。

3. 内存效率：相比使用链表，数组在连续内存中处理速度更快（CPU 缓存友好），且不需要额外的指针空间。