当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9示例 2:
输入: n = 1234
输出: 1234示例 3:
输入: n = 332
输出: 299提示:
0 <= n <= 109
题解
思路
先看示例：1234->1234, 98->89, 322->299, 798->789.
求解的思路是，从后往前遍历n的位数(即个十百千），那么原数n满足的单调递增，在从后往前遍历时，会变成递减，当有不满足条件的情况时：
- 如
n=98，那么结果位中的十位肯定不能是9，而应该是9-1=8，而结果的十位8已经<n中的百位9，所以结果的个位可以直接赋值为9，得到89； - 如
n=322，32不满足，那么结果中的百位最大只能是2，既然结果中的百位为2<n中的百位3，那么结果的十位和个位都可以取最大的9，得到299。
设n=798，当前位为cur（初始为个位8），前一位为prev（十位9），
- 如果
cur<prev，即8<9，说明不满足，则更新前一位：prev=prev-1，即9更新为8，同时记录不满足的当前位：cur为个位。 cur>=prev，这两位满足单调递增，不做操作
重复操作，直到遍历完，接下来从记录不满足的位开始，直接修改为9。
实现
n从后往前拆分，得到个位，十位，百位...用数组b记录，如n=98，b=[8,9]，n=1234,b=[4,3,2,1]。拆分方法是n>0时，循环b[bidx++]=n%10; n/=10;
接下来从前往后遍历数组b，比较当前下标i（当前位cur）和下标i+1（前一位prev）
- 如果
b[i]<b[i+1]，更新prev：b[i+1]=b[i+1]-1;记录不满足的当前位idx9=i;
循环结束后计算结果，将之前拆分的过程反过来：res*=10; res+=b[i]，还需要从记录不满足的位开始，直接赋值为9。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
int b[11]={0};//存放拆分的位
int bidx=0;
//从后往前拆分
while(n>0){
b[bidx++]=n%10;
n/=10;
}
int idx9=-1;
for(int i=0;i<bidx;++i){
//原数是否单调递增，记录第一个不满足的位置，并且修改原值
//因为从后往前拆分，所以在前面的是原数后面的
if(b[i]<b[i+1]){
b[i+1]=b[i+1]-1;
idx9=i;
}
}
int res=0;
for(int i=bidx;i>idx9;--i){
res*=10;
res+=b[i];
}
//以9填
for(int i=idx9;i>=0;--i){
res*=10;
res+=9;
}
return res;
}
};