Leetcode 738.单调递增的数字

力扣传送门(opens new window)

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

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

示例 1:

• 输入: N = 10
• 输出: 9

示例 2:

• 输入: N = 1234
• 输出: 1234

示例 3:

• 输入: N = 332
• 输出: 299

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

解题思路：

这道题可以使用贪心算法来解决。我们可以从给定的数字 N 的最高位开始，逐位向低位遍历，找到第一个违反单调递增条件的位，然后将该位减1，同时将该位后面的所有位都变为9，以保证取得的数字是小于等于 N 的最大单调递增整数。

具体的步骤如下：

1. 将数字 n 转换为字符串，方便逐位处理。
2. 从最高位开始遍历，找到第一个递减的位置，记为flag。递减的条件是当前位数字小于上一位数字。
3. 如果找到了递减的位置flag，将该位置的数字减1，并将该位置后面的所有数字都变为9。
4. 如果没有找到递减的的位置flag，说明给定的数字本身已经是一个单调递增的数字，不需要进行任何变动，直接返回即可。

代码实现：

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        int len = s.length();
        char[] chars = s.toCharArray();
        int flag = len;
        for(int i = len - 1;i > 0;i--){
            if(chars[i] < chars[i-1]){
                flag = i ;
                chars[i-1]--;
            }
        }

        for(int i = flag; i < len;i++){
            chars[i] = '9';
        }

        return Integer.parseInt(new String(chars));
    }
}