738.单调递增的数字

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        vector <int> a;
        int nn = n;
        while(n > 0) {
            int item = n % 10;
            a.push_back(item);
            n /= 10;
        }
        reverse(a.begin(),a.end());
        for (int i = 1; i < a.size(); i ++ ) {
            if (a[i] < a[i-1]) {
                int cnt = a.size() - i;
                int shift = cnt;
                int right = 0;
                while (cnt > 0) {
                    right *= 10;
                    right += 9;
                    cnt -- ;
                }
                int left = 0;
                for (int j = 0; j < i; j ++ ) {
                    left *= 10;
                    left += a[j];
                }
                left = monotoneIncreasingDigits(left - 1);
                return left * 10 * shift + right;
            }
        }
        return nn;
        // 1232 -> 1229
        // 2312 -> 2299
        // 9123 -> 8999
        // 100001 -> 
    }
};

332 -- 329 × 332 -- 299 √ 想不出了，原来是要从后往前

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int flag = s.size();
        for ( int i = s.size() - 1; i > 0; i -- ) {
            if (s[i-1] > s[i]) {
                flag = i;
                s[i-1] -- ;
            }
        }
        for ( int i = flag; i < s.size() ; i ++ ) {
            s[i] = '9';
        }
        return stoi(s);
    }
};

草 真优雅