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
