738. Monotone Increasing Digits (Python)

Related Topic

Greedy. String.

Description

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.)

Sample I/O

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

Methodology

Split the number into array and iterate the array. If the current number is smaller than last number (which will against the monotone increasing digits rule) then go backword of digits that we walked and compare the current number with last number until we find the last number is smaller than current number and we get the index. Now the index indicate the digit in array need to minus 1. All digits before the index will keep same and all digits after the index will become 9. We combine the three parts to get the result.

def monotoneIncreasingDigits(self, N: int) -> int:
    if N<10: return N
    number = str(N)
    index = -1
    size = len(number)
    for i in range(1,size):
        if number[i]<number[i-1]:
            index = i
            while index >0 and number[index]<=number[index-1]:
                index-=1
            break
    if index == -1: return N
    return int(number[:index]+str(int(number[index])-1)+(size-index-1)*'9')

BigO

Time complexity : O(N).