Leetcode 738 Solution

This article provides solution to leetcode question 738 (monotone-increasing-digits)
Categories:
Tags:
Access this page by simply typing in "lcs 738" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/monotone-increasing-digits

Solution

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

        s = []
        for i, ch in enumerate(a):
            if not s or s[-1] <= int(ch):
                s.append(int(ch))
            else:
                break
        else:
            return N

        s[-1] -= 1
        while len(s) > 1 and s[-1] < s[-2]:
            s.pop(-1)
            s[-1] -= 1

        ans = int("".join([str(v) for v in s]))
        while ans * 10 + 9 <= N:
            ans = ans * 10 + 9
        return ans