Leetcode 66: plus one

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.

这个题的点在于： 当所有位都是9的时候，需要开辟一个新的vecotor，首位是1，其他位是0。
时间复杂度： O（n）空间复杂度: 一般情况下O（1），最差情况下O（n）

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        //sanity check
        if (digits.size() == 0) return digits;
        int i = 0;
        for (i = digits.size()-1; i >= 0 ; i--) {
            if (digits[i] < 9) {
                digits[i] += 1;
                return digits;
            } else {
                digits[i] = 0;
            }
        }
        if (i < 0) {
            vector<int> rst(digits.size()+1, 0);
            rst[0] = 1;
            return rst;
        }
        return digits;
    }
};