题目
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10 输出: 9
示例 2:
输入: N = 1234 输出: 1234
示例 3:
输入: N = 332 输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。
解题
方法一：累加法
由于结果要求各位数字单调递增，那么这些数字必然形如 a0a1a2……an (1 <= a0 <= a1 <= a2 <= …… <= an <= 9)
显然有：
可见最终结果必然是若干个形如 11……11 的数字相加所得。
本题中，最大的n为10^9，所以，可以从111111111开始依次累加，如果继续累加将导致结果超过n，则去掉一个1继续循环。总累加次数不超过9次。
这样子做的好处是使得，不管怎么加，得到的res都是单调递增的
class Solution { public: int monotoneIncreasingDigits(int n) { int ones=111111111; int res=0; for(int i=0;i<9;i++){ while(res+ones>n){ ones/=10; } res+=ones; } return res; } };
方法二：贪心
局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。
class Solution { public: int monotoneIncreasingDigits(int N) { string strNum = to_string(N); // flag用来标记赋值9从哪里开始 // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行 int flag = strNum.size(); for (int i = strNum.size() - 1; i > 0; i--) { if (strNum[i - 1] > strNum[i] ) { flag = i; strNum[i - 1]--; } } for (int i = flag; i < strNum.size(); i++) { strNum[i] = '9'; } return stoi(strNum); } };
