738.单调递增的数字 monotone-increasing-digits

问题描述

738.单调递增的数字

解题思路

将该数字的每一位数字变成数组dec<int>的一部分，然后依次遍历，直到dec[i] > dec[i + 1]，然后将dec[i + 1]及以后的数字都变成9，如果dec[i] == dec[i - 1] == ··· == dec[j]，就将dec[j]--，其余全设置为9。

代码

class Solution {
private:
    void vec_dec(int n, vector<int> &res) {
        while (n != 0) {
            res.push_back(n % 10);
            n = n / 10;
        }
    }
    int ten(int i) {
        int res = 1;
        while (i != 0) {
            i--;
            res *= 10;
        }
        return res;  
    }
public:
    int monotoneIncreasingDigits(int n) {
        vector<int> dec;
        vec_dec(n, dec);
        std::reverse(dec.begin(), dec.end());
        if (dec.size() <= 1)
            return n;
        for (int i = 0; i < dec.size() - 1; i++) {
            if (dec[i] > dec[i + 1]) {
                // dec[i] = dec[i + 1];
                int j = i + 1;
                int k = i - 1;
                while (j < dec.size())
                    dec[j++] = 9;
                while (i > 0 && dec[i] == dec[i - 1])
                    dec[i--] = 9;
                if ((i > 0 && dec[i] > dec[i - 1]) || i == 0)
                    dec[i] = dec[i] - 1;
                break;
            }      
        }
        int sum = 0;
        for (int i = 0; i < dec.size(); i++) {
            sum += dec[i] * ten(dec.size() - i - 1);
        }
        return sum;
    }
};