单调递增的数字

发表于 分类于 阅读次数：

单调递增的数字（难度：中等）

1

方法：

2
代码
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        s = list(str(N))
        i = 1
        while i<len(s) and s[i-1] <= s[i]:
            i += 1
        while 0 < i < len(s) and s[i-1] > s[i]:
            s[i-1] = str(int(s[i-1])-1)
            i-=1
        s[i+1:] = '9'*(len(s)-i-1)
        return int(''.join(s))

3
复杂度

时间复杂度：O(D)。其中 D≈logN，N 是数字的长度。 空间复杂度：O(D)。