力扣：738. 单调递增的数字（贪心）

题目：

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9
示例 2:

输入: n = 1234
输出: 1234
示例 3:

输入: n = 332
输出: 299

提示:

0 <= n <= 109

思路：

题意

首先先理解题意是什么，
给定一个整数n 要求返回一个从左往右单调递增的整数（后一位也可以等于前一位），并且n要尽可能的大（在<=n中最大且满足条件）
例：n = 1234
n本来就是从左往右单增，所以直接返回n本身1234
例：n = 322
要想n从左往右单增，则百位的3必须减1，此时百位3确定下来了，十位和个位是单增（包括等于）但222不是最大，最大是299，所以十位的2和个位的2要变成9

题意如果想清楚了，这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢？
从前向后遍历的话，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。

这里需要注意一点
题目中给出的n是整型，需要转化成字符型，字符型不能直接±

完整代码：

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        n = str(n)  # 将整数转换为字符串方便处理
        flag = len(n)  # 初始化标志位为字符串长度
        # 从后向前遍历字符串
        for i in range(len(n) - 1, 0, -1):
            # 如果当前数字比前一个数字小，说明需要修改前一个数字
            if n[i] < n[i - 1]:
                flag = i  # 更新标志位为当前位置i
                # 将前一个数字减1，然后将后面的数字都变为9
                n = n[: i - 1] + str(int(n[i - 1]) - 1) + n[i:]
        # 将标志位后面的所有数字都变为9
        for i in range(flag, len(n)):
            n = n[:i] + '9' + n[i + 1:]
        return int(n)  # 返回处理后的结果

暴力法（超时，但也是一个思路）：

class Solution:
    def checkNum(self, num):
        max_digit = 10
        # 逐个提取num的各个位上的数字
        while num:
            digit = num % 10
            # 如果当前位的数字小于等于max_digit，则更新max_digit为当前位的数字
            if max_digit >= digit:
                max_digit = digit
            else:
                return False
            num //= 10
        return True

    def monotoneIncreasingDigits(self, N):
        # 从N开始递减到1
        for i in range(N, 0, -1):
            # 对每个数字调用checkNum方法进行检查
            if self.checkNum(i):
                return i
        return 0

复杂度分析：

• 时间复杂度：O(n)，n 为数字长度
• 空间复杂度：O(n)，需要一个字符串，转化为字符串操作更方便