leetcode 738. Monotone Increasing Digits

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:

Input: N = 10
Output: 9

Example 2:

Input: N = 1234
Output: 1234

Example 3:

Input: N = 332
Output: 299

Note: N is an integer in the range [0, 10^9].

---

首先将给定的数字转换成字符串
应用贪心策略，查找第一个比下一位小的位置，这样就能保证在这一位以前，均为升序排列，而对于这一位，退位(s[i]-1)操作，再将剩余位置用9填充。
如果在字符串中出现 当前位数与下一位相等 的情况，记录这个其第一次出现的位置，退位时也在其第一次出现的位置退位，并以9填充

---

class Solution {
private:
    int strTonum(string s){
        int ans=0;
        int len=s.size();
        for(int i=0;i<len;i++)
            ans=ans*10+(s[i]-'0');
        return ans;
    }
    string numTostr(int N,int dig){
        string ans(dig,'+');
        int pos=dig-1;
        while(N){
            char c=N%10+'0';
            ans[pos]=c;
            pos--;
            N/=10;
        }
        return ans;
    }
    int numOfDigit(int N){
        int num=0;
        while(N){
            num++;
            N/=10;
        }
        return num;
    }
public:
    int monotoneIncreasingDigits(int N) {
        if(N<10)
            return N;
        int len=numOfDigit(N);
        string num=numTostr(N,len);
        int index=-1;
        string temp(len,'0');
        bool flag=false;
        for(int i=0;i<len-1;i++){
            if(num[i]<num[i+1]){
                index=i;
                temp[i]=num[i];
            }else{
                if(num[i]==num[i+1]){
                    temp[i]=num[i];
                    continue;
                }
                else{
                    index++;
                    temp[index]=num[i]-1;
                    index++;
                    flag=true;
                    break;
                }
            }
        }
        if(!flag)
            return N;
        else{
            for(int i=index;i<len;i++)
                temp[i]='9';
            return strTonum(temp);
        }
    }
};

---

测试样例

test:567321
ans:566999

test:23344551
ans:23344499

test:54321
ans:49999

test:120
ans:119

test:0
ans:0