# Time:  O(logn) = O(1)
# Space: O(logn) = O(1)

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        nums = map(int, list(str(N)))
        leftmost_inverted_idx = len(nums)
        for i in reversed(xrange(1, len(nums))):
            if nums[i-1] > nums[i]:
                leftmost_inverted_idx = i
                nums[i-1] -= 1
        for i in xrange(leftmost_inverted_idx, len(nums)):
            nums[i] = 9
        return int("".join(map(str, nums)))

@@ -42,16 +42,464 @@
 = O(1)%0A%0A
+# Given a non-negative integer N,%0A# find the largest number that is less than or equal to N with monotone increasing digits.%0A#%0A# (Recall that an integer has monotone increasing digits if and only%0A# if each pair of adjacent digits x and y satisfy x %3C= y.)%0A#%0A# Example 1:%0A# Input: N = 10%0A# Output: 9%0A#%0A# Example 2:%0A# Input: N = 1234%0A# Output: 1234%0A#  %0A# Example 3:%0A# Input: N = 332%0A# Output: 299%0A#   %0A# Note: N is an integer in the range %5B0, 10%5E9%5D.%0A%0A
 class So

Update monotone-increasing-digits.py