刷题记录（LeetCode738 单调递增的数字）

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• 0 <= n <=

 关键词：贪心，数学

思路：为了方便比较，先把原数各位置上的数分解成单个数字存储在数组中。从低位向高位遍历，如果当前位（低位）的数字小于前一位（高位）的数字，将当前位的数字改成9,。需要注意的是，既然这一位改成9了，那么为了保证单调递增的特性，当前位之前（更低位）的所有位置的数字也要全部改成9。如此遍历完一遍后，得到的数组就是最终结果的各位数字。之后再把每位数字取出来变成最终结果就行了。

需要注意的是，n=0需要单独处理。另外类型开long，不然会溢出。

题解如下：

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        vector<long> digits;
        while(n != 0) {
            digits.push_back(n % 10);
            n /= 10;
        }
        if(digits.size() == 0) return 0;
        for(int i = 0; i < digits.size() - 1; i++) {
            if(digits[i] < digits[i+1]) {
                for(int j = i; j >= 0; j--) digits[j] = 9;
                digits[i+1] -= 1;
            }
        }
        long flag = 1,res = 0;
        for(int i = 0; i < digits.size(); i++) {
            res += digits[i] * flag;
            flag *= 10;
        }
        return res;
    }
};