738.单调递增的数字

代码随想录

题解思路：

感觉贪心算法就是常识题，咋一看题目很简单，但是真要把原理说清楚确实很不简单，里面的逻辑确实值得推敲，第一次做这道题，听卡哥视频讲解完全一脸懵，为什么为什么为什么这样操作，然后把卡哥的思路捋清之后，顺着代码逻辑捋一遍过程就好很多了，其中需要注意以下几点：
1、由于String字符串是不可变的字符序列，不能直接修改字符元素，因此需要转换成对应的字符数组对其每个位置元素进行修改
2、设置的标志flag一定要大于数组长度的大小，保证输入数字的符合单调递增的情况下，不会修改字符数组中的内容，直接原样输出数字
3、遍历数组的时候需要从后往前遍历，这样更新当前字符后，可以继续与前一个字符继续比较，从而保证前一个数字小于当前遍历的数字，这也是为什么不从前往后遍历
4、只对前一个字符大于当前字符的情况下，将前一个字符进行减1的操作
5、定义一个标志位，使得从该标志位之后的所有位置的元素都将其修改为字符9，这里不能直接操作numArr[i]='9'，因为如果遇到1000的话，就会输出900，显然是不正确的，因此需要将修改字符位之后的所有位置都统一修改为字符'9'才正确
6、不能使用Arrays.toString(numArr)将字符数组转换为字符串，以输入的是10为例，输出将会是"[0,9]"，因为这个方法返回的是一个表示数组内容的字符串，其中包含了字符数组的所有元素和其他字符（比如中括号和逗号）。

class Solution {public int monotoneIncreasingDigits(int n) {String num = String.valueOf(n); //将整型n的值转换为对应的字符串形式char[] numArr = num.toCharArray(); //由于String字符串是不可变的字符序列，不能直接修改字符元素，因此需要转换成对应的字符数组对其每个位置元素进行修改int flag = numArr.length; //保证输入数字的符合单调递增的情况下，不会修改字符数组中的内容，直接原样输出数字for(int i = numArr.length - 1 ; i > 0; i--){ //从后往前遍历，这样更新当前字符后，可以继续与前一个字符继续比较，从而保证前一个数字小于当前遍历的数字，这也是为什么不从前往后遍历if(numArr[i-1] > numArr[i]){ //只对前一个字符大于当前字符的情况下，将前一个字符进行减1的操作numArr[i-1]--;flag = i; //定义一个标志位，使得从该标志位之后的所有位置的元素都将其修改为字符9，这里不能直接操作numArr[i]='9'，因为如果遇到1000的话，就会输出900，显然是不正确的，因此需要将修改字符位之后的所有位置都统一修改为字符'9'才正确}}for(int i = flag; i < numArr.length; i++){  //如果输入数字符合单调递增，那么flag也没重新赋值，由于i<numArr.length限制，使得不会进入此循环，直接原样输出数字即可numArr[i] = '9';}// return Integer.parseInt(Arrays.toString(numArr)); 不能使用Arrays.toString(numArr)将字符数组转换为字符串，以输入的是10为例，输出将会是"[0,9]"，因为这个方法返回的是一个表示数组内容的字符串，其中包含了字符数组的所有元素和其他字符（比如中括号和逗号）return Integer.parseInt(new String(numArr));}
}