017 · Plus One

algorithm
Published

May 12, 2026

My First Thoughts

这个题第一眼看起来有点像：

额？不就是整数加一吗？

数组 digits 表示一个整数，比如：

[1,2,3]

就是 123。

那么加一之后应该变成：

[1,2,4]

第一反应是从最后一位开始处理。

如果最后一位不是 9，那直接把最后一位加一就行：

[1,2,3] -> [1,2,4]

如果最后一位是 9，就会产生进位。

比如：

[1,2,9] -> [1,3,0]

所以可以从右往左看：

  • 当前位不是 9，就把它加一，然后结束
  • 当前位是 9，就把它变成 0，继续往前进位

初步写代码时，很容易想到用 pop 和 append 去改数组里的元素。

如果沿用这个“从最后一位开始递推进位，并且用 pop 把原来的数字拿出来，再把新数字放回去”的思路，代码可以改成这样：

def plusOne_by_pop_insert(digits: list[int]) -> list[int]:
    for i in range(len(digits) - 1, -1, -1):
        value = digits.pop(i)

        if value != 9:
            digits.insert(i, value + 1)
            return digits

        digits.insert(i, 0)

    digits.insert(0, 1)
    return digits

这是最初的想法：每次先把当前位置的数字取出来，再把更新后的数字放回原位置。

但有一个 Python 语法点要改：append 只能把元素加到数组末尾，不能指定下标。

也就是说，Python 里没有这种写法：

digits.append(i, value)

如果要把元素放回指定下标，应该用：

digits.insert(i, value)

另一个想法是：把整个数组先转成整数，加一之后，再拆回数组。

比如：

[4,3,2,1] -> 4321 -> 4322 -> [4,3,2,2]

这个思路在 Python 里好像也能做，因为 Python 的整数可以很大。

如果沿用这个思路，代码可以写成：

def plusOne_by_integer(digits: list[int]) -> list[int]:
    number = 0

    for digit in digits:
        number = number * 10 + digit

    number += 1

    return [int(ch) for ch in str(number)]

这里的关键不是用 10 ^ k。在 Python 里，^ 不是乘方，而是按位异或。乘方要写成 10 ** k。

不过更简单的方式是：从左到右读数字时，每读到一位，就让当前数字乘以 10，再加上这一位。

Why That Is Not Enough

先说 pop 和 insert 这个版本。

它是可以做对的，但对这道题来说动作太重了。

这道题不需要真正改变数组中间的长度，也不需要把某一位拿出来再放回去。

比如我们想把下标 i 上的数字改成 0，直接写：

digits[i] = 0

想把它加一，也直接写：

digits[i] += 1

如果用 pop(i)，Python 会先删除这个位置，后面的元素会往前移动。

再用 insert(i, value)，Python 又要把元素插回去，后面的元素可能再次移动。

所以虽然这个写法能得到正确答案，但它比直接改 digits[i] 更绕，也更慢。

再看“转成整数”的思路。

它能表达题意，但不是这道题真正想训练的东西。

题目给的是“数字数组”，重点是让我们在数组上模拟加法进位。并且在很多语言里，整数长度是有限的。如果 digits 很长，直接转成普通整数可能会溢出。

所以更稳的做法是：不要把整个数组转成整数，而是只处理加一可能影响到的末尾几位。

Final Idea

从数组最后一位开始，向前遍历。

如果当前位不是 9：

  1. 把当前位加一
  2. 直接返回 digits

因为没有继续进位，前面的数字都不需要动。

如果当前位是 9：

  1. 把当前位改成 0
  2. 继续看前一位

例如：

[1,2,9]

从最后一位开始：

9 -> 0，需要进位
2 -> 3，进位结束

结果是：

[1,3,0]

如果整个数组都是 9，比如：

[9,9,9]

循环会把它们全部改成：

[0,0,0]

这说明最高位也产生了进位。最后只需要在最前面补一个 1：

[1,0,0,0]

Why It Works

加一只会影响数组末尾连续的 9，以及这些 9 前面的第一位非 9 数字。

比如：

[2,3,9,9]

末尾两个 9 都会变成 0，它们前面的 3 会变成 4：

[2,4,0,0]

更前面的 2 不会受影响。

所以从右往左处理时：

  • 遇到 9，说明进位还要继续
  • 遇到非 9，加一后进位结束，可以立刻返回
  • 如果一直没有遇到非 9，说明原数组全是 9，结果一定是 1 后面跟一串 0

Code

def plusOne(digits: list[int]) -> list[int]:
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] != 9:
            digits[i] += 1
            return digits

        digits[i] = 0

    return [1] + digits

Complexity

Time \(O(n)\) — 最坏情况下需要从最后一位检查到第一位
Space \(O(1)\) — 除了返回结果需要的数组外，只用了常数额外变量

Takeaway

遇到“数字数组加一”时，不要急着把数组转成整数。真正关键的是从末尾开始模拟进位：不是 9 就加一返回，是 9 就变成 0 继续往前。

← Quiz