Monotone increasing digits: largest such number up to n

A number has monotone increasing digits when each digit is less than or equal to the digit to its right, as in 1234 or 1129. Two parts, the second building on the first.

Interface

Unless you agree on a different interface with the interviewer, assume:

• is_monotone(n: int) -> bool — whether the digits of n never decrease from left to right.
• largest_monotone(n: int) -> int — the largest number <= n with monotone increasing digits.

Example

is_monotone(1234)       ->  True
is_monotone(332)        ->  False
largest_monotone(10)    ->  9
largest_monotone(1234)  ->  1234
largest_monotone(332)   ->  299
largest_monotone(120)   ->  119

Constraints

• 0 <= n <= 10^9.
• Single-digit numbers are monotone.

Clarifying questions

• Is "increasing" strict or non-strict? (Non-strict here: 1129 counts.)
• Can n be negative?
• May I work on the decimal string, or should I use arithmetic only?

What a strong answer covers

• Part 1: one pass over adjacent digits, O(d) for d digits.
• Part 2: the greedy fix. Find the first place a digit is bigger than the next, step back while the previous digit is equal, decrease that digit by one and set every digit after it to 9. O(d).
• Why stepping back over equal digits matters (332 -> 299, not 329).
• Why counting down from n until a monotone number appears is too slow in the worst case.
• Tests: single digit, already monotone, 10, runs of equal digits, 1000000000.

Follow-ups

• Return the smallest monotone number >= n.
• Count how many monotone numbers are <= n (digit DP).
• Strictly increasing digits instead.