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

首先，我们需要从数组的最后一位开始遍历，将当前位的值加1。如果当前位的值小于9，说明加1后不会产生进位，直接返回数组即可。否则，将当前位的值设为0，并继续遍历前一位。

如果遍历完整个数组后，仍然没有返回结果，说明最高位产生了进位，需要在数组的最前面插入一个新的元素1。

具体实现如下：

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

时间复杂度分析： 遍历数组的时间复杂度为O(n)，其中n为数组的长度。所以总的时间复杂度为O(n)