当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。
给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
示例 3:
输入: n = 332
输出: 299
提示:
0 <= n <= 109
首先先理解题意是什么,
给定一个整数n 要求返回一个从左往右单调递增的整数(后一位也可以等于前一位),并且n要尽可能的大(在<=n中最大且满足条件)
例:n = 1234
n本来就是从左往右单增,所以直接返回n本身1234
例:n = 322
要想n从左往右单增,则百位的3必须减1,此时百位3确定下来了,十位和个位是单增(包括等于)但222不是最大,最大是299,所以十位的2和个位的2要变成9
题意如果想清楚了,这道题就好办了。
此时是从前向后遍历还是从后向前遍历呢?
从前向后遍历的话,举个例子,数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。
那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299
确定了遍历顺序之后,那么此时局部最优就可以推出全局,找不出反例,试试贪心。
这里需要注意一点
题目中给出的n是整型,需要转化成字符型,字符型不能直接±
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
n = str(n) # 将整数转换为字符串方便处理
flag = len(n) # 初始化标志位为字符串长度
# 从后向前遍历字符串
for i in range(len(n) - 1, 0, -1):
# 如果当前数字比前一个数字小,说明需要修改前一个数字
if n[i] < n[i - 1]:
flag = i # 更新标志位为当前位置i
# 将前一个数字减1,然后将后面的数字都变为9
n = n[: i - 1] + str(int(n[i - 1]) - 1) + n[i:]
# 将标志位后面的所有数字都变为9
for i in range(flag, len(n)):
n = n[:i] + '9' + n[i + 1:]
return int(n) # 返回处理后的结果
暴力法(超时,但也是一个思路):
class Solution:
def checkNum(self, num):
max_digit = 10
# 逐个提取num的各个位上的数字
while num:
digit = num % 10
# 如果当前位的数字小于等于max_digit,则更新max_digit为当前位的数字
if max_digit >= digit:
max_digit = digit
else:
return False
num //= 10
return True
def monotoneIncreasingDigits(self, N):
# 从N开始递减到1
for i in range(N, 0, -1):
# 对每个数字调用checkNum方法进行检查
if self.checkNum(i):
return i
return 0