738.单调递增的数字

想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。注意实际上是之后的都要为9

想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。

//C++ 自己模拟的，有点笨，可以直接int转string，用flag标记索引为9的位置，避免重复更新9
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        vector<int> res;
        int i = 0;
        while (n > 0) {
            res.push_back(n % 10);
            n = n / 10;
        }
        for (int i = 1; i < res.size(); i++) {
            if (res[i] > res[i - 1]) {
                res[i]--;
                for (int j = i - 1; j >= 0; j --)
                res[j] = 9;
            }
        }
        int ans = 0;
        for (int i = res.size() - 1; i >= 0; i--) {
            ans *= 10;
            ans += res[i];
        }
        return ans;
    }
};
//优化版本，更好利用语言的特性
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string ss = to_string(n);
        int flag = ss.size();
        for (int i = ss.size() - 1; i > 0; i--) {
            if (ss[i] < ss[i - 1]) {
                ss[i - 1]--;
                flag = i;
            }
        }
        for (int i = ss.size() - 1; i >= flag; i--) {
            ss[i] = '9';
        }
        int ans = stoi(ss);
        return ans;
    }
};

968.监控二叉树

一刷过