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. 從最后一位開始加，可以認(rèn)為+ 1 == 從一開始的進(jìn)位carry = 1.
2. 先得到加上carry 以后的值，carry重置為0； 如果結(jié)果 >= 10, 那么當(dāng)前位結(jié)果為0， carry == 1；否則當(dāng)前位結(jié)果 == digit[index] + carry
3. 如果全部掃描完了，carry還是為1，那么說明input是 99, 999這種情況。那么直接生成一個(gè)新的array，長(zhǎng)度為digits.length + 1, 再把首位設(shè)為1，返回這個(gè)新的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;
    }
}