单调递增的数字
找到一个比目标值小的最大递增数列
递归法
从左到右遍历，找符合递增的部分，
当发现不符合的部分，不符合部分都置9
找到符合部分-1的最大递增数（后面都置9要借位）
例：输入668841
发现6688部分符合递增，但是从4开始不符合，因此41变成99
之后找到6688-1的最大递增（后面99要借1）为6679
在和最后两个99合并，得到667999
class Solution { public: int monotoneIncreasingDigits(int n) { if(n<10) return n; string num = to_string(n); string result ; result += num[0]; int flag = 0; //是否符合标志位，当不符合递增的时候，后面都置9 for(int i=1 ;i<num.size();i++) //遍历 { if(num[i] >= num[i-1] && flag==0) //找到符合递增的部分 { result += num[i]; } else if(flag==0) //找到第一个不符合递增的数 ，并求之前符合部分-1最大递增 { result = to_string(monotoneIncreasingDigits(stoi(result)-1) ); flag = 1; //设置为不符合 } if(flag == 1) //不符合后面全都置9 { result += '9'; } } return stoi(result); } };
贪心法 反向遍历
局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
class Solution { public: int monotoneIncreasingDigits(int n) { if(n<10) return n; string num = to_string(n); int flag; for(int i=num.size()-1 ; i >=1 ;i--) { if(num[i] < num[i-1]) { flag = i; num[i-1] -= 1; } } for(int i = flag ; i<num.size() ;i++) { num[i] = '9'; } return stoi(num); } };
二刷
class Solution { public: int monotoneIncreasingDigits(int n) { if(n<10) return n; string s = to_string(n); int flag=s.size(); for(int i=s.size()-1 ; i>0 ;i--) { if(s[i] < s[i-1]) { s[i-1]--; flag = i; } } for(int i=flag ; i<s.size();i++) s[i] = '9'; return stoi(s); } };
