力扣738-单调递增的数字
一、原题题目
1.1 题目
给定一个非负整数 N,找出小于或等于N的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。
(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)
1.2 示例
示例1:
输入:N = 10
输出:9示例2:
输入:N = 1234
输出:1234示例3:
输入:N = 332
输出:299
说明:N 是在[0, 109]范围内的一个整数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/monotone-increasing-digits
二、解题思路
2.1 题目意思理解
按照题目意思,我们从前往后去分析数据,如果当前位数上的值小于后一位的值时,那么当前位值要 -1,右边的所有位置 9 。否则按照位数向右递归。
2.2 详细代码(Java)
public class Solution {
public int monotoneIncreasingDigits(int N) {
// 将 int 转换成字符串再转换成字符数组
char[] strN = Integer.toString(N).toCharArray();
int i = 1;
// 找到前一个数值大于当前数值的位置
while (i<strN.length && strN[i-1]<=strN[i]) i++;
// 原数字不是单调递增的
if (i<strN.length){
// 前一个数值大了,执行减一操作,减一后要检验之前的
while (i > 0 && strN[i-1]>strN[i]){
strN[i-1]--;
i--;
}
// 讲最终修改后的位置之后都改为 9
for (i+=1;i<strN.length;i++) strN[i]='9';
}
return Integer.parseInt(new String(strN));
}
}
2.3 算法执行结果

三、总结分析
从前往后遍历,如果前面的值大于后面的值就把当前位数减一然后把后面的值变成9,以此类推