738. Monotone Increasing Digits

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:

Input: N = 10
Output: 9

Example 2:

Input: N = 1234
Output: 1234

Example 3:

Input: N = 332
Output: 299

Note: N is an integer in the range [0, 10^9].

// Greedy
int monotoneIncreasingDigits(int N) { // time: O(n); space: O(n)
    string str = to_string(N);
    int n = str.length(), pos = n;
    for (int i = n - 1; i >= 0; --i) {
        if (str[i - 1] <= str[i]) continue;
        pos = i;
        --str[i - 1];
    }
    for (int j = pos; j < n; ++j) {
        str[j] = '9';
    }
    return stoi(str);
}