738. 单调递增的数字

题目链接

题目描述：
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:
输入: N = 10
输出: 9

示例 2:
输入: N = 1234
输出: 1234

示例 3:
输入: N = 332
输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

难点：

思路1：
暴力遍历，超时。

public int monotoneIncreasingDigits(int n) {if (n>=0 && n <= 9) {return n;}while(n > 0) {if (isIncrease(n)) {return n;}n--;}return 0;
}public boolean isIncrease(int n) {char[] chars = String.valueOf(n).toCharArray();for (int i = 1; i < chars.length; i++) {if (chars[i-1] > chars[i]) {return false;}}return true;
}

思路2：
确定贪心思路

例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

再举个例子，数字1000，从后向前遍历：
位置2和3，00没问题
位置1和2，00没问题
位置0和1，10，不满足非单增，记录当前i的位置
最后将记录位置i及其之后所有位置的值都赋为9

public int monotoneIncreasingDigits(int n) {if (n >=0 && n <= 9) return n;char[] chars = String.valueOf(n).toCharArray();int flag = chars.length;//记录需要赋值为“9”的起始位置for (int i = chars.length-1; i > 0; i--) {if (chars[i] < chars[i-1]) {flag = i;chars[i-1] -= 1;}}//赋值“9”for (int i = flag; i < chars.length; i++) {chars[i] = '9';}int result = Integer.parseInt(String.valueOf(chars));return result;
}

时长：
30min

收获：
修改数值的各位数字为递增策略