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()总结单调递增的数字是贪心算法的典型应用通过从高位到低位遍历并调整数字来找到最大单调递增的数字。