Monotone Increasing Digits

Problem

Return the largest integer less than or equal to n whose decimal digits are non-decreasing from left to right.

Find the first position where a digit drops, decrement the digit before the drop, and set every following digit to 9 while back-propagating any new violation. If the digits are already non-decreasing, return n unchanged.

Hint

After decrementing, a new violation may appear further left, so keep backtracking.

Test cases

case 1

in: [10]

expected: 9

case 2

in: [1234]

expected: 1234

case 3

in: [332]

expected: 299

case 4

in: [100]

expected: 99

case 5

in: [120]

expected: 119

case 6

in: [0]

expected: 0

Starter codePython

def monotone_increasing_digits(n):
    # Your code here
    pass

6 test cases · run your code against them in the editor