leetcode

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))

以上⬆️


发布于2020-12-15 18:04:12