738.单调递增的数字
要求：
保证最大的一个数，它满足 每个位数都是递增的
思路1：
为了减少时间复杂度，当时打算，先判断最大的位数，从大-》小，看以后的位数是否满足当前数比前一个数大
思路2：
其实前面再往后想想：就是如果当前的数不满足，直接降级，然后后面都是9 就可以了 ——》一定要好好看例子结果
代码：
1 // 要求：返回小于N 但是这个数字的每个位数都是单调递增的 2 // 3 // 难点：怎么判断他是单调递增？ 4 // 1，每个数字转成字符串，然后进行比对 5 // 2，对每个数字都取余数123 ： 先%10 得到3 然后/10 变成12 6 // 7 // 思路： 8 // 1，先从n往下遍历，如果满足这个条件，那么就可以 9 // 10 // 思路2： 11 // 1，先对目标节点遍历，获得它的数值，然后必须满足第一个数字是小于等于原数值，后面要求>=前一个 12 // 13 // 思路3； 14 // 1，如果当前节点不满足，那么就把比这个高的节点降级，然后此节点变成9 15 // 注意 100 -> 99 变成 一个标志 16 // 17 18 19 int monotoneIncreasingDigits(int n) { 20 if (n == 0) return 0; 21 22 string n_str = to_string(n); 23 int flag = 0; 24 for (int i = n_str.size() - 1; i >= 1; i--) 25 { 26 // 目的：直到找到最大的 n-1,9这样的情况，然后9后面的都变成9 27 if (n_str[i] < n_str[i - 1]) 28 { 29 n_str[i - 1] = n_str[i - 1] - 1; 30 flag = i; 31 } 32 } 33 34 for (int i = flag; i < n_str.size() && flag!=0; i++) 35 { 36 n_str[i] = '9'; 37 } 38 39 return stoi(n_str); 40 }