LeetCode 738 单调递增的数字
题目链接:738. 单调递增的数字 - 力扣(LeetCode)
【解题思路】
-
需要采用从后往前的遍历
-
如果发现该数字的前一位比后一位大,那么前一位就做-1处理,后一位变为9
-
注意:千万不要将start初始化成0!!因为如果if逻辑没有走到,那么下面的for循环会从0开始将所有位的数值赋值成0!!!
【解题步骤】
-
1.将传进来的int值转化为String类型,目的是为了方便遍历
-
2.将转为string的值再转为char数组,在char数组上原地修改,效率更高
-
3.定义一个start变量,记录我们需要从哪里开始修改数值为9
-
4.从值的倒数第二位开始从后往前遍历(因为需要比较当前位和下一位的大小,从倒数第一位遍历会越界):
-
如果当前位的数大于下一位的数:
-
当前位的数-1
-
start=i+1
-
-
-
5.从start当前的位置开始遍历整个数组:
-
将start位置以及之后的位置的值全改为9
-
-
6.return Integer.parseInt(String.valueOf(chars));
【代码部分】
class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = s.length();for(int i = s.length() - 2; i >= 0 ; i--){if(chars[i] > chars[i+1]){chars[i]--;start = i+1;}}for(int i = start ; i< s.length() ; i++){chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}