LeetCode 738. 单调递增的数字

题目

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈单调递增。

例：
输入: n = 10
输出: 9

输入: n = 332
输出: 299

方法：贪心算法

• 将数字 n 的每位数存储在列表中
• 从后到前循环遍历。若前一个数的大小大于后一个数的大小，那么将前一个数减一，同时，后一个数即其之后的数均变为 9
  ※ 不能从前到后遍历：若 int(n[i-1]) > int(n[i])，那么 int(n[i-1])-1，可能会导致小于 int(n[i-2])

class Solution(object):
    def monotoneIncreasingDigits(self, n):
        n = list(str(n))
        for i in range(len(n)-1, 0, -1):
            if int(n[i-1]) > int(n[i]):
                n[i-1] = str(int(n[i-1])-1)
                n[i:] = '9' * (len(n) - i)
        return int(''.join(n))

参考

代码相关：https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html