)
前言
LeetCode 第 66 题「加一」的要求是：给定一个由整数组成的非空数组，数组按最高位在前的顺序表示一个非负整数，把这个整数加一，返回结果数组。例如[1, 2, 3]表示 123，加一后是[1, 2, 4]；[9, 9]表示 99，加一后是[1, 0, 0]。
这道题常被当作「数组遍历」的入门题，但它真正考的是进位模型：什么时候可以直接加一并返回，什么时候必须把当前位清零继续向左，什么时候需要在最前面补一位。三个分支对应三种情况，漏掉任何一个都会在特定输入上出错。
初学者最容易犯的错误是把数组转成一个整数再+1，然后拆回数组。这个做法在数组很短时「看起来能用」，但数组长度可能达到一百位，远超int、long long甚至__int128的范围，转换过程本身就是溢出。另一类错误是循环变量用无符号类型，写成for (std::size_t i = digits.size() - 1; i >= 0; --i)，当i减到 0 之后再自减会回绕成极大值，循环永远不会结束。
本文从进位模型讲起，给出原地修改与不修改输入两种写法，再延伸到「加任意整数」和「字符串大数相加」，最后列出常见错误。所有复杂度都按标准语义分析，不涉及任何运行时间测量。
一、题意拆解
题目有三个隐含约定，读题时要确认：
- 非空：数组至少有一个元素，所以不必处理空数组。
- 无前导零：除了数字 0 本身表示为
[0]，其它情况最高位不为 0。 - 最高位在前：
digits[0]是最高位，digits[n-1]是个位。
加一运算只影响从个位开始的一段连续 9。具体来说：
- 如果个位小于 9，直接加一，其余位不变，立刻返回；
- 如果个位是 9，加一后变成 10，本位记 0，进位 1 传给前一位；
- 如果连续一段（可能一直到最高位）都是 9，它们全部变 0，并在最前面插入一个 1。
这个观察就是全部算法：从右往左扫描，遇到第一个小于 9 的位就加一并返回；扫描完整个数组都没返回，说明全是 9，在最前面插入 1。
二、为什么不能转成整数
假设数组长度是 100，每一位都是 9。这个数约等于 10 的 100 次方，而 64 位无符号整数的上限约是 1.8×10 的 19 次方。用long long或unsigned long long都装不下，转换时会发生截断或溢出。
即便数组很短，转换也有其它问题：需要额外的乘加循环，复杂度没有变好；有符号整数溢出是未定义行为，不能依赖「溢出后回绕」这种假设。逐位处理没有这些负担，而且天然支持任意长度。
| 方案 | 时间 | 额外空间 | 长度上限 | 正确性风险 |
|---|
转成long long再加一 | O(n) | O(n) | 约 19 位 | 长数组必然溢出 |
| 逐位进位（原地） | O(n) | O(1) | 仅受内存限制 | 无 |
| 逐位进位（新数组） | O(n) | O(n) | 仅受内存限制 | 无 |
三、原地修改的写法
// 适用于 C++17
#include <vector>
class Solution {
public:
std::vector<int> plusOne(std::vector<int>& digits) {
// 从个位开始向左扫描
for (int i = static_cast<int>(digits.size()) - 1; i >= 0; --i) {
if (digits[i] < 9) {
++digits[i]; // 不需要进位，直接加一并结束
return digits;
}
digits[i] = 0; // 这一位是 9，加一后变 0，继续向左进位
}
// 走到这里说明所有位都是 9，需要在最高位前补 1
digits.insert(digits.begin(), 1);
return digits;
}
};几个细节值得说明：
- 循环变量用
int而不是std::size_t。digits.size()是无符号的size_t，减一之后如果数组非空没问题，但循环条件i >= 0对无符号类型永远成立，会死循环。题目保证数组非空，所以static_cast<int>(digits.size()) - 1不会得到负数（前提是长度不超过int的上限，实际题目远达不到）。 return digits;返回的是std::vector<int>的副本。函数签名返回类型是值类型，这里会触发一次拷贝；由于返回值优化（RVO）和移动语义，编译器通常会消除或转为移动，但语义上它是一次返回。- 全 9 的情况用
insert在头部插入。std::vector::insert在头部插入的时间复杂度是 O(n)，因为要移动所有已有元素。整个算法最坏情况下也是 O(n)，所以总复杂度仍是 O(n)。
如果不想修改输入，可以传值：
// 适用于 C++17
#include <vector>
std::vector<int> plusOneCopy(std::vector<int> digits) {
for (int i = static_cast<int>(digits.size()) - 1; i >= 0; --i) {
if (digits[i] < 9) {
++digits[i];
return digits;
}
digits[i] = 0;
}
digits.insert(digits.begin(), 1);
return digits;
}参数按值传递，函数内部操作的是副本，调用者的数组不受影响。代价是一次 O(n) 的拷贝，但代码更安全，适合「入参不可变」的接口约定。
四、用反向迭代器改写
如果不喜欢下标与符号的纠缠，可以用反向迭代器：
// 适用于 C++17
#include <vector>
std::vector<int> plusOneIter(std::vector<int> digits) {
for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
if (*it < 9) {
++(*it);
return digits;
}
*it = 0;
}
digits.insert(digits.begin(), 1);
return digits;
}rbegin()指向最后一个元素，rend()指向第一个元素之前的位置。反向迭代器的++是向左移动，正好符合「从个位向高位」的扫描方向，也不会出现无符号下溢。这段代码的可读性通常比下标版本更好。
五、扩展到「加任意整数」
把「加一」推广成「加 k」，进位就不再是 0 或 1，而是一个可能大于 1 的进位值：
// 适用于 C++17
#include <vector>
std::vector<int> addInt(std::vector<int> digits, int k) {
int carry = k;
for (int i = static_cast<int>(digits.size()) - 1; i >= 0 && carry > 0; --i) {
const int sum = digits[i] + carry;
digits[i] = sum % 10;
carry = sum / 10;
}
while (carry > 0) {
digits.insert(digits.begin(), carry % 10);
carry /= 10;
}
return digits;
}这里有两个循环：第一个处理数组内部的进位，第二个处理「进位超出最高位」的情况。比如[9, 9]加 1，第一个循环结束后digits是[0, 0]、carry是 1，第二个循环把 1 插到最前面。如果 k 很大（比如 12345），第二个循环会依次插入多位，注意插入顺序：每次插入的是carry % 10，然后carry /= 10，最终得到的是正确的高位序列。
这个版本假设 k 非负。如果要支持负数，需要先比较被减数与减数的大小，再决定做加法还是减法，复杂度会上升不少，属于另一类「大数运算」的范畴。
六、复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|
| 从右往左扫描 | O(n) | 最多检查 n 位 |
| 头部插入 1 | O(n) | 需要移动所有元素 |
| 整体 | O(n) | 最坏情况全 9，扫描加插入 |
| 额外空间 | O(1) | 原地版本只用几个标量 |
最坏情况是数组全为 9：扫描 n 位全部置 0，再插入一位并移动 n 个元素，总共约 2n 次操作，仍是 O(n)。最好情况是个位小于 9，只做一次比较和一次自增，O(1)。
常见坑点
1. 把数组转成整数再计算
❌long long v = 0; for (int d : digits) v = v * 10 + d; v += 1;再拆回数组 ✅ 逐位处理进位
数组长度可以到一百位，任何内置整数类型都装不下。转换过程中的乘法本身也会溢出，而有符号溢出是未定义行为。
2. 无符号循环变量导致死循环
❌for (std::size_t i = digits.size() - 1; i >= 0; --i)✅for (int i = static_cast<int>(digits.size()) - 1; i >= 0; --i)或反向迭代器
std::size_t是无符号类型，减到 0 之后再自减会回绕成一个极大值，i >= 0永远为真。这类错误在数组为空时还会直接在size() - 1处下溢。
3. 忘了全 9 需要在头部补位
❌ 循环里把 9 置 0 后直接return digits;✅ 循环结束后执行digits.insert(digits.begin(), 1);
[9, 9]加一的结果是[1, 0, 0]，长度增加了一位。如果只在原长度内处理，会得到[0, 0]，既少了最高位，数值也完全错了。
4. 加一之后没有立即返回
❌if (digits[i] < 9) { ++digits[i]; }然后继续循环 ✅if (digits[i] < 9) { ++digits[i]; return digits; }
不需要进位的位一旦加一，左边的所有位都不应该再变。继续循环会把前面的位也加一，结果偏大。
5. 认为头部插入是 O(1)
❌ 「insert(begin(), 1)只加一个元素，所以是常数时间」 ✅ 头部插入需要把已有元素整体后移，复杂度是 O(n)
std::vector是连续存储，任何非尾部插入都会移动元素，并且会使所有迭代器失效。分析复杂度时不能只看「插入了几个元素」。
6. 返回局部数组的引用
❌std::vector<int>& plusOne(std::vector<int>& digits) { ... return digits; }用在返回临时对象的场合 ✅ 返回std::vector<int>值类型
返回引用本身在参数是左值时没问题，但一旦传入临时对象或函数内部构造的数组，引用就会悬垂。返回值的写法更通用，编译器也会用 RVO 或移动避免多余拷贝。
7. 处理前导零时误删合法位
❌ 结果里出现[0, 0]就断言「有前导零，需要去掉第一个 0」 ✅ 只有题目明确要求「输出去除前导零」时才处理，且要保留单独的一个 0
本题的输入保证无前导零，输出也不应该出现前导零（除非结果就是 0，但加一之后不可能是 0）。擅自删除元素会改变数值。
8. 修改了入参却对外声称未修改
❌ 文档写「不改变输入」，实现却直接对digits自增 ✅ 需要只读语义时按值传参，或在函数内先复制一份
接口约定与实现不一致，调用方可能复用原数组做后续计算，得到的是被改过的数据。这类问题不会立刻报错，属于最难排查的一类缺陷。
总结
| 要点 | 结论 |
|---|
| 核心模型 | 从个位向左找第一个小于 9 的位，加一即止 |
| 全 9 处理 | 全部置 0，头部插入 1，长度加一 |
| 时间复杂度 | O(n)，最坏情况扫描加头部插入 |
| 空间复杂度 | 原地版 O(1)，复制版 O(n) |
| 循环变量 | 用有符号下标或反向迭代器，避免无符号下溢 |
| 整数转换 | 禁止，长数组必然溢出 |
这道题的代码只有十几行，但它把三个基本功串在了一起：边界情况（全 9）、类型细节（无符号下溢）、复杂度直觉（头部插入不是常数时间）。把「加一」的进位模型想清楚，再推广到「加任意整数」和「两个大数相加」，就是一套完整的十进制大数运算框架。写这类题时，先在纸上把[9]、[9, 9]、[1, 9, 9]、[8]四个例子走一遍，比直接敲代码更有效率。
