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))
以上⬆️