LeetCode 66. Plus One

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

解题思路

这道题模拟的是整数加一的过程。由于数组中每个元素只存储单个数字，我们需要从最低位（数组末尾）开始处理进位。

核心思路如下：

从数组的最低位（digits.length - 1）向最高位（下标 0）遍历：

1. 如果当前位小于 9，直接加一并返回结果（因为不会有进位，后面的高位无需处理）。
2. 如果当前位等于 9，将其置为 0，并继续向前一位处理进位。

如果遍历完整个数组后仍然没有返回（即所有位都是 9，例如 999），说明需要进位到更高的位。此时创建一个比原数组长一位的新数组，将首位设为 1，其余位默认为 0，即得到了结果（例如 1000）。

这个解法的巧妙之处在于：

• 利用”遇到小于 9 直接返回”的提前终止策略，避免了不必要的遍历
• 只有在全为 9 的极端情况下才需要扩容数组

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。最坏情况下需要遍历整个数组（所有位都是 9）。
• 空间复杂度：O(1)，除了最坏情况下需要创建新数组（全 9 时 O(n)），其余情况在原数组上操作。

代码

package code.J66;

public class J66 {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}