Leetcode 738.单调递增数字

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

示例：

输入: N = 10
输出: 9
输入: N = 1234
输出: 1234
输入: N = 332
输出: 299

N 是在 [0, 10^9] 范围内的一个整数。 题目连接

我啪的一下上来就是一个暴力，果不其然超时了

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        while(not self.isIncrease(N)):
            N -= 1
        return N

    def isIncrease(self, N: int) -> bool:
        n_list = list(str(N))
        L = len(n_list)
        i = 1
        while(i < L and (n_list[i] >= n_list[i-1])):
            i += 1
        return True if(i == L) else False

原来是道真的中难题，琢磨了一会，思路大概是找到不递增的index再减1，然后继续比较，然而减1又会遇到借位的问题，给我搞糊涂了，挣扎了一下去看题解。。。

思路

找到从高位到低位第一个不满足n_list[i] >= n_list[i-1]的位置，将n_list[i-1]-1，再将后面的数字都变成9,比如：

n   = 1234321
res = 1233999

但是要考虑一种情况，之前的思路也卡在这一步：n_list[i-1]-1之后可能不满足n_list[i-1] >= n_list[i-2]，比如

n    = 2333332
res  = 2299999

继续分析，如果n_list[i-1]-1之后就不满足n_list[i-1] >= n_list[i-2]，那么肯定n_list[i-1] = n_list[i-2]，所以应该往前递归找到n_list[i-1]-1之后仍满足n_list[i-1] >= n_list[i-2]的位置，再让后面的数字变成9。

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        strN = list(str(N))
        L = len(strN)
        i = 1
        # 这一步找到不递增的索引
        while(i < L and (strN[i] >= strN[i-1])):
            i += 1
        # 如果 i < L 说明不是单调递增
        if i < L:
            # 递归
            while (i > 0 and (strN[i - 1] > strN[i])):
                strN[i - 1] = str(int(strN[i - 1]) - 1)
                i -= 1
            for j in range(i + 1, L):
                strN[j] = '9'
        return int(''.join(strN))

以上⬆️