Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution

1. 从最后一位开始加，可以认为+ 1 == 从一开始的进位carry = 1.
2. 先得到加上carry 以后的值，carry重置为0； 如果结果 >= 10, 那么当前位结果为0， carry == 1；否则当前位结果 == digit[index] + carry
3. 如果全部扫描完了，carry还是为1，那么说明input是 99, 999这种情况。那么直接生成一个新的array，长度为digits.length + 1, 再把首位设为1，返回这个新的array即可。
4. 否则返回digits

class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0)
            return digits;
        
        // handle case less than like 999, 99 which after + 1 the result wont has more digits
        int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            int temp = digits[i] + carry;
            carry = 0;
            
            if (temp >= 10) {
                digits[i] = 0;
                carry = 1;
            } else {
                digits [i] = temp;
            }
        }
        
        // handle special case 999, 99, after + 1, it will have 1 more digit
        if (carry == 1) {
            int[] newDigits = new int[digits.length + 1];
            newDigits[0] = 1;
            
            return newDigits;
        }
        
        return digits;
    }
}