'''
Description: 
Autor: Au3C2
Date: 2020-12-15 10:20:07
LastEditors: Au3C2
LastEditTime: 2020-12-15 10:20:51
'''
class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        N_s = []
        n = 0
        while N:
            N_s.append(N%10)
            N = N//10
            n += 1
        N_s = N_s[::-1]
        output = [N_s[0]]
        n_o = 1
        for i in range(1,n):
            if N_s[i] >= output[i-1]:
                output.append(N_s[i])
                n_o += 1
            else:
                output[i-1] -= 1
                while i>1 and output[i-1]<output[i-2]:
                    output[i-1] = 9
                    output[i-2] -= 1
                    i -= 1
                break
        while n_o < n:
            output.append(9)
            n_o += 1
        res = 0
        output = output[::-1]
        while output:
            res = res* 10 + output.pop()
        return res       

# 贪心算法
# https://leetcode-cn.com/problems/monotone-increasing-digits/