Leetcode----贪婪

738. Monotone Increasing Digits

此题大意：求比一个自然数小且单调递增的数中最大的那个。例如对于1002来说，答案是999.对于14436来说答案是13399。

解题思路：寻找要求解答案的规律，发现，答案是原来的正数，从右向左看，第一个违反递减的数字可以减1，然后后面全部用9补齐。

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string S = to_string(N);
        int marker = S.size();//只要违反前后大小顺序,就重置后续的数并返回；
        for(int i=S.size()-1; i>0;--i)
            if(S[i]<S[i-1])
            {
                marker = i;
                S[i-1] =S[i-1]-1;
            }
        for(int i=marker; i<S.size();++i) S[i]='9';
        return stoi(S);
    }
};