单调递增的数字-贪心738-python

没看答案。

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        def check(num):
            # 从高位到低位提取num的每一位数字
            ls = []
            while num != 0:
                ls.append(num%10)
                num = num // 10           
            ls = ls[::-1]

            # 检测相邻位是否单调递增
            tmp = ls[0]
            for i in range(1, len(ls)):
                '''
                若没有递增，则需要从这里开始把所有的低位都置0，然后再-1，因为9是最大的数字
                '''
                if ls[i] < ls[i-1]:
                    tmp = tmp * pow(10, len(ls[i:]))
                    return tmp - 1
                tmp = tmp * 10 + ls[i]
            
            return tmp       


        while n > 9:
            # 不断调用check函数，如不符合单调递增，则返回的tmp和输入的n不相等
            # 若tmp与n相等，直接返回结果
            tmp = check(n)
            if tmp == n:
                return n
            n = tmp
        
        return n