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
