难度: Medium
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 299
提示:
0 <= n <= 109
Submission
运行时间: 21 ms
内存: 16.0 MB
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
strNum = list(str(n))
for i in range(len(strNum) - 1, 0, -1):
if strNum[i-1] > strNum[i]:
strNum[i-1] = str(int(strNum[i - 1]) - 1)
for j in range(i, len(strNum)):
strNum[j] = '9'
return int(''.join(strNum))
Explain
这个题解的思路是从数字的末尾开始，逐位进行分析。如果当前位的数字比前一位的数字小，那么就将前一位的数字减1，并将当前位以及后面的所有位都设置为9。这样可以确保修改后的数字是小于等于原数字的最大单调递增数字。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
# 将数字转换为字符列表
strNum = list(str(n))
# 从末尾开始遍历数字的每一位
for i in range(len(strNum) - 1, 0, -1):
# 如果当前位的数字比前一位的数字小
if strNum[i-1] > strNum[i]:
# 将前一位的数字减1
strNum[i-1] = str(int(strNum[i - 1]) - 1)
# 将当前位以及后面的所有位都设置为9
for j in range(i, len(strNum)):
strNum[j] = '9'
# 将修改后的字符列表转换为整数并返回
return int(''.join(strNum))
Explore
当一位数字比前一位小时，说明从这个位置开始无法维持数字的单调递增。直接减小前一位的数字并将后面的数字全部改为最大可能值（9）是为了确保在保持数值尽可能大的同时，修改后的数仍然满足单调递增的条件。如果不减小前一位而是采用其他操作，可能会使得最终的数值更小，或者逻辑更加复杂且难以实现。
将当前位及之后的所有位设置为9，是因为一旦减小了前一位，那么后面的位设置为最大值9可以使得修改后的数字尽可能大。由于前一位已经减小，即使后续位全为9，整个数字也保证是小于原始数字的。这样操作确保了结果既是单调递增的，又是小于原数字的最大可能值。
如果最高位也需要减小，该策略依然有效。即使是最高位减1，其后所有位设为9仍然会形成一个小于原始数字且尽可能大的单调递增数字。例如从2803减小到2799，尽管2803的最高位2未改变，但类似地，从9200减小到8999也是有效的，即使最高位9变成了8。
在Python中，整数类型（int）是动态的，可以处理非常大的数字而不会像其他一些语言那样遇到整数溢出的问题。因此，在使用Python处理这类问题时，通常不需要担心整数溢出的问题，除非数字超出了语言处理的范围，这在实际情况中极为罕见。