每日一题20201215（738. 单调递增的数字）

738. 单调递增的数字

image-20201215143631260

思路

咱也不管什么贪心什么的，只说几种情况:

情况1:

数字本身是递增的，那么直接return就可以了

1234 -> 1234

情况2:

数字先增后减

这个时候只需要找到第一个递减的位置，然后将其-1然后后面的位数都补为9即可

323 -> 299

情况3:

含有重复数字:  668831

需要找到递减的地方: 3， 然后往回数，找到第一个8，然后改为: 667, 后面补9即可

情况4:

1000，这种需要少一位的，其实和上面一样的处理方式，高位-1，比如1-1=0，后面补9，转为int后就少了一位

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        # 这层优化可以去掉
        if N < 10:
            return N
        s = str(N)
        i = 1
        # 首先找到第一个开始递减的数字
        while i < len(s) and int(s[i]) >= int(s[i-1]):
            i += 1
        # 然后回溯找到真正递减开始的位置，比如668811, 此时i指向1，实际上应该找到第一个8
        while i > 1 and s[i-1] == s[i-2]:
            i -= 1
        # 如果i已经走到末尾了，说明字符串是递增的
        if i == len(s):
            return N
        # s[:i-1] 注意这个不包括i-1, 即不改变的递增部位
        # str(int(s[i-1])-1) 这个是递增的最高点，对他-1
        # len(s[i:]) * '9' 后面的补9即可
        # 最后加起来转为int
        return int(s[:i-1]+str(int(s[i-1])-1)+len(s[i:]) * '9')

image-20201215145022490