66. 加一

题目地址(66. 加一)

https://leetcode.cn/problems/plus-one/

题目描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

前置知识

公司

• 暂无

思路

关键点

• 从右往左找到最后一个连续的9，下一位非9，直接+1返回
• 如果没有找到，说明全是9，则直接新建一个数组，将最高位置为1，直接返回

代码

• 语言支持：Go

Go Code:

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

复杂度分析

令 n 为数字位数。

• 时间复杂度：
• 空间复杂度：最坏情况为