738 - Monotone Increasing Digits

#medium

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.

Example 1:
Input: n = 10
Output: 9

Example 2:
Input: n = 1234
Output: 1234

Example 3:
Input: n = 332
Output: 299

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string( n );
        if ( str.size() == 1 ) return n;
        int flag = -1; // 紀錄開始都為9的位置
        for ( int i = str.size() - 1; i > 0; i-- ) {
            if ( str[i-1] > str[i] ) {
                str[i-1]--;
                flag = i;
            }
        }

        if ( flag != -1 ) {
            for ( int i = flag; i < str.size(); i++ ) {
                str[i] = '9';
            }
        }

        return stoi(str);
    }
};