# LC 738. Monotone Increasing Digits

### [Problem link](https://leetcode.com/problems/monotone-increasing-digits/)

###### tags: `leedcode` `python` `c++` `medium` `Greedy`

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

Given an integer <code>n</code>, return the largest number that is less than or equal to <code>n</code> 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

**Constraints:**

- `0 <= n <= 10^9`

## Solution 1 - Greedy
#### Python

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = list(str(n))

        for i in range(len(s) - 1, 0, -1):
            if s[i - 1] > s[i]:
                s[i - 1] = str(int(s[i - 1]) - 1)
                s[i:] = '9' * (len(s) - i)
        
        return int(''.join(s))

#### C++

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strN = to_string(n);

        int flag = strN.size();
        for (int i = strN.size() - 2; i >= 0; i--) {
            if (strN[i] > strN[i + 1]) {
                strN[i]--;
                flag = i + 1;
            }
        }
        for (int i = flag; i < strN.size(); i++) {
            strN[i] = '9';
        }
        return stoi(strN);
    }
};

>### Complexity
>n = s.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
sol1:
ex: 65234

4 -> 4
34 -> 34
234 -> 234
5234 -> 4999
64999 -> 55999

[代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.md)