66. Plus One

题目描述：给一个用非空数组表示的非负整数，使它加1。数组无前导0，按下标从小到大存储该数高到低位。

分析：最低位加1后，从低位到高位遍历该数，对每一位处理其低一位的进位，时间复杂度O(n)，空间O(1)。其中反向遍历示意图：

代码：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        add(digits, 1);
        return digits;
    }
    void add(vector<int>& digits, int x)
    {
        int c = x;
        //rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素，rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置
        for(auto it = digits.rbegin(); it != digits.rend(); it ++)          
        {
            *it += c;
            c = *it / 10;
            *it %= 10;
        }
        if ( c > 0) digits.insert(digits.begin(), 1);       //原数最高位在原数加1后有进位，加个位数进位顶多为1
    }
};