0066. Plus One

题目信息

题号:
  1. 加一

难度:

Easy

主题:

数组、十进制进位、反向扫描

原题:

LeetCode 0066

重点:

从整数还原限制,推导到只处理十进制末尾进位链

题目重述

非空数组 digits 按从最高位到最低位的顺序表示一个非负十进制整数。除整数 0 外,数组没有前导零。 返回该整数加一后的数字数组。

约束为 1 <= digits.length <= 100、0 <= digits[i] <= 9。

自建示例

输入:digits = [3,4,8]
输出:[3,4,9]

最低位小于 9,加一后不会继续产生进位。

输入:digits = [8,9,9]
输出:[9,0,0]

末尾两个 9 依次变为 0,进位最终由最高位 8 吸收。

输入:digits = [9,9]
输出:[1,0,0]

全部原有数位都传出进位,因此结果需要增加一个最高位。

C++ 实现

#include <vector>

class Solution {
private:
    std::vector<int> copyAndPropagate(
        const std::vector<int>& digits
    ) {
        std::vector<int> result = digits;

        for (int index = static_cast<int>(result.size()) - 1;
             index >= 0;
             --index) {
            if (result[index] < 9) {
                ++result[index];
                return result;
            }
            result[index] = 0;
        }

        result.insert(result.begin(), 1);
        return result;
    }

    std::vector<int> mutateInPlace(std::vector<int>& digits) {
        for (int index = static_cast<int>(digits.size()) - 1;
             index >= 0;
             --index) {
            if (digits[index] < 9) {
                ++digits[index];
                return digits;
            }
            digits[index] = 0;
        }

        digits.insert(digits.begin(), 1);
        return digits;
    }

public:
    std::vector<int> plusOne(std::vector<int>& digits) {
        return mutateInPlace(digits);
    }
};

题解

整数还原限制

最直观的做法是把数组还原成普通整数,加一后再拆成数字数组。但数组最多包含 100 个十进制数位,远超固定宽度 整数的表示范围。即使最终操作只有加一,中间的整数还原仍会溢出。

数组本身已经给出了十进制数位,因此只需模拟竖式加法中的进位传播。

末尾进位链

加一从最低位开始。当前位只有两种情况:

  • 数位小于 9:该位增加 1,不再产生进位;

  • 数位等于 9:该位变为 0,并把进位继续传向左侧。

所以真正可能变化的部分只是数组末尾连续的 9,以及它左侧第一个非 9 数位。例如:

[4,8,9,9]
     ^^^^^

末尾两个 9 变成 0,数位 8 增加为 9,更高位 4 保持不变。

扫描不变量

从右向左扫描到下标 index 时,右侧已经处理过的数位全部属于原数组末尾连续的 9,并已被正确改写为 0; 当前仍有一个值为 1 的进位等待处理。

若当前数位小于 9,它可以吸收这个进位。该位加一后不会再产生新进位,因此左侧更高位无需改变,算法可以立即 返回。

若当前数位等于 9,它加一后应变为 0,进位继续存在,不变量在下一轮仍成立。

全 9 情况

若扫描越过最高位仍未返回,说明原数组的每一位都是 9:

99...9 + 1 = 100...0

循环已经把原有数位全部改写为 0,只需在数组最前面插入 1。结果长度从 n 增加到 n + 1,并且这也是 唯一会扩展数组长度的情况。

原地修改

copyAndPropagate 先复制输入,再在副本中传播进位。它保持调用者的数组不变,语义清晰,但需要保存一个完整 工作副本。

题目接口允许修改 digits,因此主方法 mutateInPlace 直接覆盖原数组。普通情况只改写末尾一段;全 9 情况还需要在首部插入 1。公开入口调用该方法,避免无必要的整数组复制。

结果规范

输入除单个 0 外没有前导零。普通情况不会把原最高位改成 0;全 9 情况新增的最高位是 1。因此两种分支都会 返回规范的十进制表示。

数字 0 也由同一逻辑覆盖:[0] 的最低位小于 9,直接变为 [1]。

方法关系

两种实现使用完全相同的进位不变量,区别只在结果存储位置:

  • 复制方案保持输入不变;

  • 原地方案复用输入数组,减少工作空间。

优化的核心不是改变扫描次数,而是识别出加一只影响末尾进位链,并在接口允许时直接复用原数组。

复杂度分析

设数组长度为 n。

复制方案需要 O(n) 时间复制数组,最坏再扫描全部数位;总时间为 O(n),工作副本占用 O(n) 空间。

原地方案最坏扫描全部数位,时间为 O(n)。除返回数组本身外只使用常数个变量,额外空间为 O(1);全 9 情况下首部插入会移动原有元素,但仍属于 O(n) 时间。