【LeetCode738】738. 单调递增的数字【贪心】

传送门

738. 单调递增的数字

思路

从后往前遍历，遇到后面的小于前面的就讲后面的全部变成9即可。

AC代码

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string s = to_string(N);
        int len = s.size();
        for(int i = len-1; i >= 1; i--){
            if(s[i]<s[i-1]){
                s[i-1]--;
                for(int j = i; j < len; j++){
                    s[j] = '9';
                }
            }
        }
        int ans = stoi(s);
        return ans;
    }
};