数字单调递增链接：https://leetcode-cn.com/problems/monotone-increasing-digits给定一个非负整数N，判断它是否小于或等于等于N的最大整数，这个整数需要满足其位数单调递增的要求。（我们说一个整数单调递增当且仅当每个相邻数字中的数字x和y满足x<=y。）示例1：输入：N=10输出：9示例2：输入：N=1234输出：1234示例3：输入：N=332输出：299解释：N是[0,10^9]范围内的整数。暴力破解的意思很简单，所以我首先想到的就是暴力破解。我给大家暴力一波，结果超时！代码如下：classSolution{private:boolcheckNum(intnum){intmax=10;while(num){intt=num%10;if(max>=t)max=t;elsereturnfalse;num=num/10;}returntrue;}public:intmonotoneIncreasingDigits(intN){for(inti=N;i>0;i--){if(checkNum(i))returni;}return0;}};时间复杂度：O(n*m)m为n的数长度空间复杂度：O(1)贪心算法题目要求最大单调小于等于N的自增整数，则以一个两位数为例.例如：98，一旦出现strNum[i-1]>strNum[i]（非单调递增），先令strNum[i-1]--，则strNum[i]为9，所以这个整数为89，小于98的最大单调递增整数。如果把这一点想清楚了，这道题就好办了。LocalOptimum：在strNum[i-1]>strNum[i]的情况下，令strNum[i-1]--，则strNum[i]为9，可以保证这两位成为最大的单调递增整数。全局最优：得到小于等于N的最大单调递增整数。但是这里局部最优导致全局最优，还需要其他条件，就是遍历的顺序，标记的哪一位开始统一变为9。这时候是不是从前面遍历到向后还是从后向前？如果是从前向后遍历，如果遇到strNum[i-1]>strNum[i]，让strNum[i-1]减一，但此时如果strNum[i-1]减一一，它可能小于strNum[i-2]。这个有点抽象。比如数字：332，如果从前向后遍历，那么就变成了329，此时2比前3小了，真正的结果应该是299。所以从前向后遍历会改变已经遍历的结果！那么从后往前遍历就可以复用上次比较的结果。从后向前遍历332的值变为：332->329->299遍历顺序确定后，那么此时就可以在全局情况下引入局部最优。如果找不到反例，请尝试贪婪。C++代码如下：classSolution{public:intmonotoneIncreasingDigits(intN){stringstrNum=to_string(N);//flag用来标记赋值9从哪里开始//设置为这个默认值，是为了防止第二次forloopwhenflagisnotset赋值的情况下，执行intflag=strNum.size();for(inti=strNum.size()-1;i>0;i--){if(strNum[i-1]>strNum[i]){flag=i;strNum[i-1]--;}}for(inti=flag;i
