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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Mathematics

Greedy algorithms

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

Solutions:
class Solution:

	def monotoneIncreasingDigits(self, N):
		arr = [int(ch) for ch in str(N)]
		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]))


class Solution:

	def monotoneIncreasingDigits(self, N):
		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):
		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):
		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):
		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):
		l = list(str(N))
		length = len(l)
		for i in range(length):
			l[i] = ord(l[i]) - ord('0')
		index = -1
		for i in range(length - 1):
			if l[i] > l[i + 1]:
				index = i
				break
		if index == -1:
			return N
		j = -1
		for i in range(index, -1, -1):
			j = i
			if i > 0 and l[i] == l[i - 1]:
				continue
			break
		l[j] -= 1
		for i in range(j + 1, length):
			l[i] = 9
		res = 0
		for i in range(length):
			res = res * 10 + l[i]
		return res


class Solution:

	def monotoneIncreasingDigits(self, N):
		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):
		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)