难度：★★★☆☆
类型：数组
方法：数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

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

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

解答

需要经过两次遍历。

第一次遍历，从最高位开始，寻找连续非递减子串的最大长度，找到不再连续非递减的位置。

第二次遍历，从第一次遍历找到的分界点开始向左遍历，做退位相减，直到最高位。

最后，将分界点以后的所有位置成9即可。

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        S = list(map(int, str(N)))

        i = 0
        while i < len(S) - 1 and S[i] <= S[i+1]:
            i += 1
        while 0 <= i < len(S) - 1 and S[i] > S[i+1]:
            S[i] -= 1
            i -= 1
        S[i+2:] = [9] * (len(S) - i - 2)
        return int("".join(map(str, S)))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析