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

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

&nbsp;
Example 1:

Input: n = 10
Output: 9


Example 2:

Input: n = 1234
Output: 1234


Example 3:

Input: n = 332
Output: 299


&nbsp;
Constraints:


	0 &lt;= n &lt;= 109


class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        num = list(str(n))
        for i in range(len(num)-1):
            # Step1: When don't meet the condition, num[i]-=1 and repalce all num left into '9' and directly return
            # However, there is the case that num[i-1]==num[i], which will make num[i]-1<num[i-1]
            # So, traverse back to find the num that its num[i-1] != num[i](to make sure num[i-1]<=num[i]-1), then do step1 and return
            if num[i] > num[i+1]:
                while i >= 1 and num[i-1] == num[i]:
                    i -= 1
                num[i] = chr(ord(num[i])-1)
                return int(''.join(num[:i+1]+['9']*(len(num)-i-1)))
        return n
class Solution {
    public int monotoneIncreasingDigits(int n) {
        int position;
        int digitInTheNextPosition;
        while ((position = getThePositionNotSatisfied(n)) != -1) {
            digitInTheNextPosition = ((int) (n / Math.pow(10, position - 1))) % 10;
            n -= Math.pow(10, position - 1) * (digitInTheNextPosition + 1);
            n -= n % Math.pow(10, position);
            n += Math.pow(10, position) - 1;
        }
        return n;
    }

    public int getThePositionNotSatisfied(int n) {
        int k = 10;
        int position = 0;
        while (n > 0) {
            if (k < n % 10) {
                return position;
            } else {
                k = n % 10;
                n /= 10;
                position++;
            }
        }
        return -1;
    }
}
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
            if(n < 10) return n;

            string s = to_string(n);

            for(int i = s.size() - 2; i >= 0; i--) {
                   if(s[i] > s[i+1]) {
                       s[i]--;
                       for(int j = i + 1; j < s.size(); j++) s[j] = '9';
                   }
            }
        int ans = stoi(s);
        return ans;
    }
};
var monotoneIncreasingDigits = function(n) {
    let arr = String(n).split('');
    for (let i=arr.length-2; i>=0; i--) {
        if (arr[i]>arr[i+1]) {
            arr[i]--;
            for(let j=i+1; j<arr.length; j++) arr[j]='9';
        }
    }
    return Number(arr.join(''));
};
Monotone Increasing Digits