738. 单调递增的数字

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

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

输入: n = 10
输出: 9

我的解法

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        std::vector<int> num;
        while (n) {
            int cur = n % 10;
            n = n / 10;
            num.insert(num.begin(), cur);
        }
        if (num.size() == 1) return n;
        int first = -1;
        int left = 0;
        int right = 1;
        for (; right < num.size(); ) {
            if (num[left] < num[right]) {
                first = -1;
                left++;
                right++;
            }
            else if (num[left] == num[right]) {
                if(first == -1 || num[first] != num[left]){
                    first = left;
                }
                left++;
                right++;
            }
            else {
                if (first == -1) {
                    num[left]--;
                    while (right < num.size()) {
                        num[right++] = 9;
                    }
                }
                else {
                    num[first++]--;
                    while (first < num.size()) {
                        num[first++] = 9;
                    }
                }
            }
        }
        int l = num.size() - 1;
        first = 0;
        n = 0;
        while (first < num.size()) {
            n += num[first] * pow(10,l);
            l--;
            first++;
        }
        return n;
    }
};

标准解法

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i] ) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};