代码随想录 -- 贪心 -- 单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

思路：

• 首先将正数n转化为字符串类型；
• 定义一个flag：标记flag以及之后的位数都是9；
• 从后向前遍历字符串n，如果当前的位数小于他上一位，将上一位减1，更新flag为当前索引；
• 从flag遍历字符串，将flag及之后位数都改为9.

class Solution(object):def monotoneIncreasingDigits(self, n):strn=str(n)flag=len(strn)for i in range(len(strn)-1,0,-1):if strn[i]<strn[i-1]:strn=strn[:i-1]+str(int(strn[i-1])-1)+strn[i:]flag=ifor i in range(flag,len(strn)):strn=strn[:i]+'9'+strn[i+1:]return int(strn)