LeetCode 单调递增的数字题解

LeetCode 单调递增的数字题解

题目描述

给定一个非负整数 N，找出小于或等于 N 的最大单调递增的数字。

示例：

输入：N = 10
输出：9

解题思路

方法：贪心

思路：

• 从高位到低位遍历数字。
• 如果发现某一位比下一位大，则将这一位减 1，并将后面的所有位设置为 9。
• 重新从高位开始检查，直到没有发现任何问题。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

代码实现

def monotone_increasing_digits(n): digits = list(str(n)) marker = len(digits) for i in range(len(digits) - 1): if digits[i] > digits[i + 1]: marker = i + 1 while i >= 0 and digits[i] > digits[i + 1]: digits[i] = str(int(digits[i]) - 1) i -= 1 break for i in range(marker, len(digits)): digits[i] = '9' return int(''.join(digits)) # 测试 def test_monotone_increasing_digits(): N = 10 print(monotone_increasing_digits(N)) # 输出：9 if __name__ == "__main__": test_monotone_increasing_digits()

总结

单调递增的数字是贪心算法的典型应用，通过从高位到低位遍历并调整数字来找到最大单调递增的数字。