题目描述

原题链接：738. 单调递增的数字

解题思路

（1）暴力法

以此遍历对比。对比方式是用当前末尾和上一个末尾的数对比，初始化时，让上一个记录末尾的数为10，从而可实现从最后一个位数的数，对比到第一个位数的数。

class Solution {
public:
    bool checkNum(int num) {
        int maxNum = 10;        // 第一个数先和10比，从而让每个数能按逻辑和前一个数比
        while(num) {            
            int t = num % 10;                       // 获取末尾位数的数值
            if(maxNum >= t)     maxNum = t;         // 和前一位比比前一位小，继续向下比，大于则false
            else                return false;
            num /= 10;                              // 除10
        }
        return true;
    }
    int monotoneIncreasingDigits(int n) {
        for(int i = n; i > 0; i--) {
            if(checkNum(i)) {
                return i;
            }
        }
        return 0;
    }
};

时间复杂度：$O(n\ast m)$
空间复杂度：$O(1)$

暴力法会报错。

（2）贪心算法

根据位数之间的关系，当num[i - 1] > num[i]时，例如：78，此时从77-70都不满足题中条件，而最大可满足条件的数则是69，具体操作是让num[i]=9，再让num[i - 1]–实现。

根据上述规律，我们可以先将数字按位变成字符变成可对比的模式，设置一个变量flag记录变为9的最高位，然后从后往前依次遍历对比。

局部最优： 遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。

全局最优： 得到小于等于N的最大单调递增的整数。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        int flag = strNum.size();                   // flag标记变9的位置
        for(int i = strNum.size() - 1; i > 0; i--) {
            if(strNum[i - 1] > strNum[i]) {         // 前一位比后一位大
                flag = i;                           // 后一位变为9
                strNum[i - 1]--;                    // 前一位的位数减一
            }
        }
        for(int i = flag; i < strNum.size(); i++) { // 从flag往后变9
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

参考文章：738.单调递增的数字