LeetCode题练习与总结：加一--66-输入：digits = [0] 输出：[1] 提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

二、解题思路

1. 首先，我们需要遍历数组的每一位数字，从最低位（数组的最后一个元素）开始。
2. 对于每一位数字，我们将其加一。如果加一后的结果小于10，那么直接更新该位的数字，并且结束循环，因为我们已经完成了加一操作。
3. 如果加一后的结果等于或大于10，说明发生了进位，我们需要将当前位的数字更新为0，并且继续处理下一位（即向前进位）。
4. 如果在遍历完整个数组后，仍然有进位（即数组中所有的位都已经加一，且最后一个位加一后仍然等于或大于10），我们需要在数组的开头添加一个1，表示进位到了最高位。

三、具体代码

public class Solution {
    public int[] plusOne(int[] digits) {
        // 从数组的最后一个元素开始，向前遍历
        for (int i = digits.length - 1; i >= 0; i--) {
            // 如果当前位加一后小于10，直接更新并结束循环
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            } else {
                // 如果当前位加一后等于或大于10，发生进位
                digits[i] = 0; // 将当前位更新为0，并继续向前一位进位
            }
        }
        // 如果所有的位都已经加一，且仍然有进位，需要在数组开头添加一个1
        int[] result = new int[digits.length + 1];
        result[0] = 1; // 在新数组的第一个位置添加1
        return result;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 该算法的主要操作是遍历整数数组的每一位数字，并对其进行加法操作。这个操作是线性的，即它与输入数组的长度成正比。
• 遍历数组的时间复杂度为 O(n)，其中 n 是数组 digits 的长度。
• 由于在遍历过程中可能需要遍历整个数组，或者在最坏的情况下（即数组中的每个数字都是9）需要遍历整个数组并再进行一次操作（在数组前面添加一个新元素）。
• 所以总的时间复杂度仍然是 O(n)。

2. 空间复杂度

• 空间复杂度主要取决于存储操作的额外空间需求。
• 在大多数情况下，我们只需要原始数组 digits 的空间来存储结果，因此空间复杂度为 O(n)。
• 但是，在最坏的情况下，当数组中的每个数字都是9时，我们需要创建一个新的数组来存储结果（因为需要在数组前面添加一个1），这将导致额外的 O(n) 空间需求。
• 因此，总的空间复杂度为 O(n)。

五、总结知识点