[数据结构与算法]2021-09-30：加一。给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数

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

福大大 答案2021-09-30：

自然智慧即可。当数组全是9的时候，需要开辟新的数组。其他情况，不需要开辟空间。
时间复杂度：O(n)。
额外空间复杂度：O(1)。全是9的情况下是O(n)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    digits := []int{9, 9, 9}
    ret := plusOne(digits)
    fmt.Println(ret)
}

func plusOne(digits []int) []int {
    n := len(digits)
    for i := n - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }
    ans := make([]int, n+1)
    ans[0] = 1
    return ans
}

执行结果如下：

左神java代码