本文共 1817 字，大约阅读时间需要 6 分钟。

1. 问题描述：

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/monotone-increasing-digits

2. 思路分析：

① 首先想到的是从N这个数字往前找，依次检查N之前的数字是否满足单调递增的条件，假如满足那么返回这个数字即可，但是提交上去后面比较大的数字超时了

②  第二个比较容易想到的是找出数字后面开始逆序的位置，这个时候需要将前面的数字减去1，看一下是否满足条件，比如1276，逆序的位置为3，所以将前面的7这个数字减去1得到6而这个时候减去1之后是满足单调递增所以这个方法大体上是可行的，但是也会遇到这样的情况，比如数字12333332，这个时候我们只是减去了一个1的话那么结果就是错误的，因为有可能前面的数字减去1之后导致不是单调递增了，所以这个时候需要使用循环继续比较当前位置的数字与前面一个数字的大小关系，依次减去1直到所有的位置都是单调递增的，最后根据记录的逆序的位置index计算出结果，[0:index]这些位置的数字是顺序的，直接计算出结果即可，后面[index:len(nums)]的位置都是9，将两部分的结果结合起来就是要求解的答案了

3. 代码如下：

class Solution:    def solve(self, N: int):        nums = list()        while N > 0:            # 使用insert函数往列表开始位置添加元素            nums.insert(0, N % 10)            N //= 10        return nums    def monotoneIncreasingDigits(self, N):        nums = self.solve(N)        # 逆序遍历        index = len(nums)        for i in range(len(nums) - 1, 0, -1):            if nums[i] < nums[i - 1]:                nums[i - 1] -= 1                index = i        res = 0        for i in range(0, index):            res = res * 10 + nums[i]        for i in range(index, len(nums)):            res = res * 10 + 9        return res

超时代码：

class Solution:    def solve(self, num):        # 使用循环从后往前判断每一位数字的大小情况        pre = 10 ** 9        while num > 0:            if num % 10 > pre: return False            pre = num % 10            # 每一次都除以10这样可以取出每一位上的数字是多少            num //= 10        return True    def monotoneIncreasingDigits(self, N: int) -> int:        # 其实这道题目可以使用从N往前找判断每一位数字是否递增的即可, 主要是模拟整个过程        while N >= 0:            if self.solve(N): return N            N -= 1        return -1

转载地址：http://ulgr.baihongyu.com/