LeetCode 738.单调递增的数字

LeetCode 738.单调递增的数字

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

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

示例 1:
输入: N = 10
输出: 9

示例 2:
输入: N = 1234
输出: 1234

示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/monotone-increasing-digits

问题分析：
可以先找到第一个前面的数大于后面的数，如何前面的数减1，在比较前面的前面的数。
例如：132456
第一个大于的数是3和2，此时i=2
所以3-1=2，此时比较1和3-1=2，发现1比它小，就不进行比较了
最后把剩余的数字全变成9
所以最后结果是129999

代码如下：

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strs=to_string(N);
        //to_string是把数值转化成相应的字符串
        int i=1;
        int n=strs.length();
        while(i<n&&strs[i-1]<=strs[i]) i++;
        if(i<n){
            while(i>0&&strs[i-1]>strs[i]){
                strs[i-1]-=1;
                i--;
            }
        }
        for(i+=1;i<n;i++){
            strs[i]='9';
        }
        //stoi是把n进制的字符串转化成十进制的整数
        return stoi(strs);
    }
};

**to_string **将数值转化成相应的字符串
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

stoi将n进制的字符串转换成十进制数字
stoi（字符串，起始位置，n进制），将 n 进制的字符串转化为十进制
stoi(str, 0, 2); //将字符串 str 从 0 位置开始到末尾的 2 进制转换为十进制**

stoi函数会做范围检查，所需转换的数字如果超出int范围，即超出[-2147483648,2147483648],会出现Runtime Error！！！
所以当题目输入字符串长度大于等于10位时，一定要注意！
一个可行的解决方法是使用stoll函数代替stoi，将string转化为long long int。

to_string和stoi的头文件是#include<string