📃 题目描述

题目链接：738. 单调递增的数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

🔔 解题思路

和 31. 下一个排列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 有点像，不过这题好像更简单点

暴力解法

暴力解法，将 N 不断缩小，每减小一个就判断一次是否数字是递增排序的，如果是，则直接返回

class Solution {
    public int monotoneIncreasingDigits(int n) {
        for (int i = n; i >= 0; i --) {
            if (checkNum(i)) {
                return i;
            }
        }
        return 0;
    }
	
    // 判断数字 i 的每位是否是递增的
    private boolean checkNum(int i) {
        int maxNum = 10;
        while (i != 0) {
            int temp = i % 10;
            if (temp <= maxNum) {
                maxNum = temp;
                i /= 10;
            }
            else {
                return false;
            }
        }
        return true;
    }
}

时间复杂度 O(N * M)，M 是数字 N 的长度，LeetCode 上提交会超时

贪心算法

题目需要找出小于或等于 n 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

也就是说，如果这个 n 的各个位已经是单调递增的了（前一位小于后一位），那么就要不进行任何改变

换句话说，我们要考虑的其实就是前一位比后一位大的情况：

• 局部最优：遇到 n[i - 1] > n[i]的情况，让 n[i - 1]--，然后 n[i] 直接赋值为 9，可以保证这两位变成最大单调递增整数。
• 全局最优：得到小于等于 n 的最大单调递增的整数

从前后向遍历会改变已经处理的结果，所以我们需要从后往前遍历

举个例子：

322 -> 322 -> 292

可以看到，有可能出现前一个数和后一个数相同的情况，这种情况下是符合题意的，但是如果我们不进行处理，就会出现这个例子的情况。这里最后的 2 也应该变成 9

所以我们需要一个标志位 flag，来表示 flag 及之后的数都需要变为 9，比如这个例子中的 flag 就是 1，表示下标 1 以及其之后的数，都得变成 9.

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] chars = Integer.toString(n).toCharArray();
        // flag 及之后的数都需要变为 9
        int flag = chars.length; 
        for (int i = chars.length - 1; i > 0; i --) {
            if (chars[i - 1] > chars[i]) {
                chars[i - 1] -= 1;
                flag = i;
            }
        }
		
        if (flag == arr.length) {
            return n;
        }
       
        for (; flag < chars.length; flag ++) {
            chars[flag] = '9';
        }

        // 处理 09xxx 的情况，去掉开头的 0
        if (chars[0] == '0' && chars.length > 1) {
            char[] res = new char[chars.length - 1];
            int index = 0;
            for (int i = 1; i < chars.length; i ++) {
                res[index ++] = chars[i];
            }
            return Integer.parseInt(String.valueOf(res));
        }

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

• 空间复杂度：O(N)
• 时间复杂度：O(N)