leetcode 738 单调递增的数字

昨天卡爆的一道题！！！
思路很简单，比较当前位和下一位关系，如果比下一位大，则将其减一，然后将后面的数字全变为九，卡的是相等，需要记录相等的位置。

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        # 465 --- 459 
        # 44123 --- 39999
        # 443 --- 399
        # 445 --- 445
        nums = [i for i in str(N)]
        i = 0
        sign = False # 是否有当前位大于下一位的数字，如果没有表示该数字递增。
        while i < len(nums) - 1:
            t = i
            while i + 1 < len(nums) - 1 and nums[i] == nums[i+1]:
                i += 1
            if nums[i] > nums[i+1]:
                change = t
                sign = True
                break
            else:
                i += 1
        if not sign:
            return N
        nums[change] = str(int(nums[change]) - 1)
        for i in range(len(nums)):
            if i > change:
                nums[i] = "9"
        return int("".join(nums))

补充：MMP，从后往前遍历简单，如果出现临界点问题，可改它啊！，让它满足条件继续走。

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        nums = [i for i in str(N)]
        t = len(nums) - 1
        for i in range(len(nums)-1, 0, -1):
            if nums[i] < nums[i-1]:
                nums[i-1] = str(int(nums[i-1]) - 1)
                t = i - 1
        if t != len(nums) - 1:
            for i in range(len(nums)):
                if i > t:
                    nums[i] = "9"
        return int("".join(nums))