M738-单调递增数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• 0 <= n <= 109

题解:

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strn=to_string(n);
        int len=strn.size();
        int maxindex=len;
        //这里比较巧妙的是从后向前遍历在过程中改变结果
        for (int i = len-1; i>0; i--){
            //如果本身是递增序列就不会进入这个if
            if(strn[i-1]>strn[i]){
               maxindex = i;  //这样maxindex其实是最大值的右一位
               strn[i-1]--;  //这里如果不是最大值会在后面的赋值9中替换掉
            }
        }
        for (int i = maxindex; i < len; i++)
        {
            strn[i]='9';
        }
        return stoi(strn);
    }
};

//从左到右找最大值处理不了本来就是递增序列的情况,所以要用自身对比来解决
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strn=to_string(n);
        int len=strn.length();
        int maxindex=-1;
        //这里找第一个最大位数
        for (int i = 0; i < len; i++){
            if((strn[i]-'0')>maxindex) maxindex = i;
        }
        strn[maxindex]--;
        for (int i = maxindex+1; i < len; i++)
        {
            strn[i]='9';
        }
        return stoi(strn);
    }
};