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


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

Difficulty: interview

Starter code:

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        

Solutions:
class Solution:
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         
         arr = [int(ch) for ch in str(N)] # create array from number 1234 => [1,2,3,4]
         marker = len(arr)
         
         i = len(arr)-2
         while i >= 0:
             if arr[i] > arr[i+1]:
                 marker = i+1
                 arr[i] -= 1  
             i-=1
         
         while marker < len(arr):
             arr[marker] = 9
             marker += 1
         
         return int(''.join([str(num) for num in arr]))
         
         
 #         # any number 0..9 has always monotone increasing digits
 #         if N < 10:
 #             return N
         
 #         stack = []
         
 #         # create stack of digits 1234 -> [4,3,2,1]
 #         while N:
 #             stack.append(N%10)
 #             N = N // 10      
         
 #         X = 0
 #         power_of_10 = len(stack)-1
 #         right = stack.pop()
 #         while stack:
 #             left = right
 #             right = stack.pop()
 #             if left <= right:
 #                 X += left * (10**power_of_10)
 #                 power_of_10 -= 1
 #             else:
 #                 X += (left-1) * (10**power_of_10)
 #                 X += int('9'*power_of_10)
 #                 return self.monotoneIncreasingDigits(X)
         
 #         # remaining part
 #         X += right
         
 #         return X


class Solution:
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         digits = list(map(int, str(N)))
         i = 0
         while i < len(digits) - 1 and digits[i] <= digits[i+1]:
             i += 1
         while 0 <= i < len(digits) - 1 and digits[i] > digits[i+1]:
             digits[i] -= 1
             i -= 1
         digits[i+2:] = '9' * (len(digits) - i - 2)
         return int(''.join(map(str, digits)))


class Solution:
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         n = str(N)
         pos = 0
         for i, char in enumerate(n):
             if i>0 and int(n[i])<int(n[i-1]):
                 return int("".join(n[:pos])+str(int(n[pos])-1)+"9"*(len(n)-1-pos)) if int(n[pos])>1 else int("9"*(len(n)-1-pos))
             elif i>0 and n[i] != n[i-1]:
                 pos = i
         return N

class Solution:
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         NN = ('000000000000000000' + str(N))[-11:]
         chron = '0'
         for i in range(10):
             maxpossible = int(chron[-1])
             for fill in range(int(chron[-1]),10):
                 if chron + str(fill)*(10-i) <= NN:
                     maxpossible = fill
             chron = chron + str(maxpossible)
         return int(chron)
 


class Solution(object):
     def monotoneIncreasingDigits(self, N):
         digits = []
         A = list(map(int, str(N)))
         for i in range(len(A)):
             for d in range(1, 10):
                 if digits + [d] * (len(A)-i) > A:
                     digits.append(d-1)
                     break
             else:
                 digits.append(9)
 
         return int("".join(map(str, digits)))

class Solution:
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         digits = list(int(d) for d in str(N))
         for i in range(len(digits)-1, 0, -1):
             if digits[i] < digits[i-1]:
                 for k in range (i, len(digits)):
                     digits[k] = 9
                 digits[i-1] -= 1
 
         return int(''.join([str(d) for d in digits]))

class Solution(object):
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         l = list(str(N))
         length = len(l)
         for i in range(length): l[i] = ord(l[i]) - ord('0')
 
         # get the longest non-decreasing sequence
         index = -1
         for i in range(length-1):
             if l[i] > l[i+1]:
                 index = i
                 break
         if index == -1: return N
 
         j = -1
         # identity which digit to change
         for i in range(index, -1, -1):
             j = i
             if i>0 and l[i] == l[i-1]:
                 continue
             break
         
         # make the change
         l[j] -= 1
         for i in range(j+1, length): l[i] = 9
 
         # get the result
         res = 0
         for i in range(length): res = res*10+l[i]
         return res

class Solution:
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         a = list(str(N))
         i = 1
         while i < len(a) and a[i] >= a[i-1]:
             i += 1
         while 0 < i < len(a) and a[i] < a[i-1]:
             a[i-1] = str(int(a[i-1]) - 1)
             i -= 1
         a[i+1:] = '9' * (len(a)-i-1)
         
         return int(''.join(a))

class Solution:
     def monotoneIncreasingDigits(self, N):
         """
         :type N: int
         :rtype: int
         """
         n, pos = str(N), 0
         for i, char in enumerate(n):
             if i>0 and int(n[i])<int(n[i-1]): return int("".join(n[:pos])+str(int(n[pos])-1)+"9"*(len(n)-1-pos)) if int(n[pos])>1 else int("9"*(len(n)-1-pos))
             elif i>0 and n[i] != n[i-1]: pos = i
         return N

class Solution:
     def monotoneIncreasingDigits(self, N):
         N = str(N)
         L = len(N)
         for i in range(L - 1):
             if N[i] > N[i + 1]:
                 return self.monotoneIncreasingDigits(int(N[:i] + str(int(N[i]) - 1) + '9' * (L - i - 1)))
         return int(N)