## 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]`.

b'
\n\n

#### Approach #1: Greedy [Accepted]

\n

Intuition

\n

Let\'s construct the answer digit by digit.

\n

If the current answer is say, `123`, and the next digit is `5`, then the answer must be at least `123555...5`, since the digits in the answer must be monotonically increasing. If this is larger than `N`, then it\'s impossible.

\n

Algorithm

\n

For each digit of `N`, let\'s build the next digit of our answer `ans`. We\'ll find the smallest possible digit `d` such that `ans + (d repeating) > N` when comparing by string; that means `d-1` must have satisfied `ans + (d-1 repeating) <= N`, and so we\'ll add `d-1` to our answer. If we don\'t find such a digit, we can add a `9` instead.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the number of digits in . We do work building and comparing each candidate, and we do this times.

\n
• \n
• \n

Space Complexity: , the size of the answer and the temporary string we are comparing.

\n
• \n
\n
\n

#### Approach #2: Truncate After Cliff [Accepted]

\n

Intuition

\n

One initial thought that comes to mind is we can always have a candidate answer of `d999...9` (a digit `0 <= d <= 9` followed by some number of nines.) For example if `N = 432543654`, we could always have an answer of at least `399999999`.

\n

We can do better. For example, when the number is `123454321`, we could have a candidate of `123449999`. It seems like a decent strategy is to take a monotone increasing prefix of `N`, then decrease the number before the "cliff" (the index where adjacent digits decrease for the first time) if it exists, and replace the rest of the characters with `9`s.

\n

When does that strategy fail? If `N = 333222`, then our strategy would give us the candidate answer of `332999` - but this isn\'t monotone increasing. However, since we are looking at all indexes before the original first occurrence of a cliff, the only place where a cliff could exist, is next to where we just decremented a digit.

\n

Thus, we can repair our strategy, by successfully morphing our answer `332999 -> 329999 -> 299999` with a linear scan.

\n

Algorithm

\n

We\'ll find the first cliff `S[i-1] > S[i]`. Then, while the cliff exists, we\'ll decrement the appropriate digit and move `i` back. Finally, we\'ll make the rest of the digits `9`s and return our work.

\n

We can prove our algorithm is correct because every time we encounter a cliff, the digit we decrement has to decrease by at least 1. Then, the largest possible selection for the rest of the digits is all nines, which is always going to be monotone increasing with respect to the other digits occurring earlier in the number.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the number of digits in . Each step in the algorithm is a linear scan of the digits.

\n
• \n
• \n

Space Complexity: , the size of the answer.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'