代码随想录算法训练营第三十七天| LeetCode738.单调递增的数字

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));
    }
}