单调递增的数字

找到一个比目标值小的最大递增数列

递归法

从左到右遍历，找符合递增的部分，
当发现不符合的部分，不符合部分都置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; //是否符合标志位，当不符合递增的时候，后面都置9for(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);}
};