LeetCode-738

738. 单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

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

Example

Note

• N 是在 [ 0 , 1 0 9 ] [0, 10^9] [0,109] 范围内的一个整数。

思路

1. 要满足单调递增，那么限制在于后面的数字能否取得到，所以我们从低位开始判断
2. 通过对样例进行分析，以及题意理解，可以得到这样的过程
3. 如果当前位置数值 ≥ 高一位数值，那么保持不变
4. 如果当前位置数值 < 高一位数值，那么高位数值-1，后面全部变成9
5. 实现思路不难，难点在于优雅的编码实现，下面的代码是从一位大佬那里学到的

代码如下

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        int p=1,res=N;
        while(p <= res/10)
        {
            int n = res/p %100;//得到后两位
            p*=10;
            if(n/10 > n%10)//如果前面大于后面
                res=res/p*p -1;//前面位数大小-1,后面全部为9
        }
        return res;
    }
};