🔺738.单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

示例 1:

• 输入: N = 1234
• 输出: 1234

示例 2:

• 输入: N = 332
• 输出: 299

思路

基本思想

某一个数字中的一部分出现92的情况，就不符合条件， 此时只需要将92变成89即可符合条件，变化的过程位2->9，9->8,也就是2从前面的9借了一位，让其变成最大的9，前面的9被借走一个变成8

每次只借走一个，并且被借走的那一位开始可能不小于前面，借走之后可能小于前面

例如992，开始9和9符合要求，结果中间的9被借走一位变成8，最后的2变成9，最终的数字变成989，不符合要求，所以被借走的那一位需要与前面的进行比较，防止不符合要求

这与 135.分发糖果 有点类似，因为统计左>右时，需要从后向前遍历，如果从前向后遍历，右边的更新之后，可能会造成分数少的糖果多，所以左边的需要后统计

本题也是一样的，由于当前位数被借走一个之后可能小于高一位，所以只能从后向前遍历

并且一旦当前位减小一个，后面的位数都可以变成9，这样既不会超过原来的数字又贪心的将其变成符合要求的最大数字

增加flag是因为如果有两位相等就不会借一位，此时就不会变成9，如果更高位出现了借一位变成9的情况，此时就会不符合要求，例如211，模拟一遍就知道是什么意思

借一位的思想很重要，从低位向高位遍历，一旦出现飞递增，就需要向高位借位，记录最高的借位的位置，后面的位置都可以变成9

执行流程

遵循不符合要求就向高一位借一个变成9，高一位少一个的思想

1. 从前向后遍历这个数
2. 遇到不符合要求的就向高一位借一个变成9，高一位少一个
3. 遍历到最高位结束
4. 记录最后一个被借走一个的位，后面的位都可以变成9

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string num=to_string(n);
        int flag=num.size();
        for(int i=num.size()-1;i>0;--i){
            //不符合要求
            if(num[i-1]>num[i]){
                //向前借一位
                num[i-1]-=1;
                flag=i;//后面的所有位都可以变成9
            }
        }
        for(int i=flag;i<num.size();++i){
            num[i]='9';//不能是9，必须是'9'，9的ascii是\t
        }
        return stoi(num);
    }
};

总结

一旦出现两位不符合要求，就向高位借一位，地位变成9，并且由于高位借走一位会变小，可能与更高位之间出现不合法的情况，所以需要从后向前遍历

出现特殊情况4211时，如果只借一位变成9，最终的结果会时3991，答案错误，所以需要记录最后被借走的是哪一位，后面的都拉到最大变成9即可，最终的答案会变成3999

找到最长的符合要求的递增序列，借一位，后面的变成9即可