跳到主要内容

LeetCode 66. 加一

本节目标

从最低位反向传播进位，并在不再进位时立即返回。

这道题承接模拟、递推与边界：把进位看作从最低位向高位传播的状态，并单独处理全进位的边界。

查看原题

题意与约束​

给定一个非空数组 digits，其中每个元素是一位十进制数字，数组按从最高位到最低位表示一个非负整数。将这个整数加一后，返回同样形式的数字数组。

  • 1 <= digits.length <= 100
  • 每个 digits[i] 都在 0 到 9 之间。
  • 除数字 0 本身外，最高位不会是 0。

从最低位传播进位​

加一只会先影响最低位，所以从数组末尾反向扫描。遇到小于 9 的数字时，直接加一即可；更高位和已经处理的后缀都不需要再改动。

若当前位是 9，它加一后应写成 0，同时进位继续向左传播。循环持续时，已经处理的后缀恰好全为 0；这正是进位仍未停止的状态。

为什么可以提前返回​

一旦遇到小于 9 的数字，给它加一便消除了进位。更高位从未修改，后缀已经在之前逐位改为正确的 0，整个数组已经是答案，因此可以立刻返回。

例如 [4, 3, 2, 1] 从末位开始就能返回 [4, 3, 2, 2]，不必扫描其余三位。

全是 9 时发生什么​

[9, 9] 会依次变成 [9, 0]、[0, 0]，扫描结束后仍有一个进位。此时原数组已经是所需长度的全零数组，在最前面插入 1 即得到 [1, 0, 0]。

这也是唯一需要增加数组长度的情况。

代码实现​

两份源码都从最低位反向处理；仅在进位停止时提前返回，全部为 9 时再构造新的最高位。

C++17
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> plusOne(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;
    }
};

复杂度分析​

  • 最好情况：最低位小于 9，只处理一位，时间复杂度为 O(1)。
  • 最坏情况：所有数字都是 9，需要扫描整个数组，时间复杂度为 O(n)。
  • 除返回数组本身外只使用常数变量，额外空间复杂度为 O(1)。

易错点​

  • 从最高位开始处理，无法自然表达进位方向。
  • 把 9 加一后保留为 10，忘记当前位应写为 0。
  • 所有数字都是 9 时只返回全零数组，遗漏新增最高位的 1。
  • 遇到小于 9 的数字后继续改动更高位，而不是立即返回。

模式迁移​

数位加法、大整数模拟、链表表示的数字相加都遵循同一个方向：从最低位读取旧值，写回当前位，并把是否继续进位交给更高位。若进位已经消失，应优先识别可以提前结束的位置。