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.

------------------------------------------------------------------------------------------------
这个题关键是如何进位以及判断数组的首位前是否进1。可以用一个辅助标记来帮助我们做到这些。

C++代码：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 0;
        int len = digits.size();
        for(int i = len - 1; i >= 0; i--){
            int a = digits[i];
            if(i == len - 1){
                int sum = a + carry + 1;
                digits[i] = sum % 10;
                carry = sum / 10;  //进一位。
            }
            else{
                int sum = a + carry;
                digits[i] = sum % 10;
                carry = sum / 10;
            }
        }
        if(carry != 0){  //表明前面还得进位。
            digits.insert(digits.begin(),carry);
        }
        return digits;
    }
};