LeetCode_贪心算法_中等_738.单调递增的数字

1.题目

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

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈单调递增。

示例 1：

输入: n = 10
输出: 9

示例 2：
输入: n = 1234
输出: 1234

示例 3：
输入: n = 332
输出: 299

提示：
0 <= n <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/monotone-increasing-digits

2.思路

（1）暴力穷举法
该方法比较容易想到，即可以先写一个用于判断非负整数是否是单调递增的函数，然后再从整数 n 开始遍历，如果 n 不是单调递增的，那么再判断 --n，直到找到单调递增的整数为止。不过该方法的时间复杂度较高，在 LeetCode 上提交时会出现“超出时间限制”的提示！

（2）贪心算法
方法 1 的时间复杂度太高的原因在于，需要对大量的数进行重复的是否单调递增的判断。所以想要降低空间复杂度，需要直接从问题本身入手，即想到一个可以直接从整数 n 出发，找到小于或等于 n 的最大单调递增的数字。

由于当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，称这个整数是单调递增的。所以我们采用贪心算法的思想，在对问题求解时，总是做出在当前看来是最好的选择。所以具体的步骤如下：
① 为了方便后面步骤的执行，我们先将 n 转换为字符串，然后再将其转换为字符数组 chs；
② 对于整数 n，从左往右开始遍历各位数字，找到第一个开始递减的数字 chs[i]，然后将其减一，并且将 chs[i] 之后的所有数字全部置为 9 即可，这样便找到了小于或等于 n 的最大单调递增的数字。
③ 不过需要注意一些特殊情况：

例如 n = 1444432，chs = ['1', '4', '4', '4', '4', '3', '2']
按照上面的步骤，找到的第一个开始递减的数字 chs[i] = '4'，i = 4，将 chs[i] 减一，并且将 chs[i] 之后的所有数字全部置为 9 
即有 chs = ['1', '4', '4', '4', '3', '9', '9']，此时得到的数为 1444399，这显然不是单调递增的。

出现错误的主要原因在于没有考虑到第一个开始递减的数字 chs[i] 前面还有与其相等的数，如果直接将最后一个数 chs[i] 减一，那么
前面与 chs[i] 相等的数必然大于 chs[i] 减一后的数，此时的数就不是单调递减的了。

所以如果第一个开始递减的数字 chs[i] 的前面还有与其相等的数字，那么需要找到最前面的等于 chs[i] 的数，还以 n = 1444432 举例，
往前找可以得出 i = 1，然后将 chs[1] 减一，再将后面所有的数字置为 9，即可得到 chs = ['1', '3', '9', '9', '9', '9', '9']，
那么 1399999 即为小于或等于 n 的最大单调递增的数字。
1
2
3
4
5
6
7
8
9
10

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public int monotoneIncreasingDigits(int n) {
        while (!isIncremental(n)) {
            --n;
        }
        return n;
    }
    
    //判断 n 是否是单调递增的
    private boolean isIncremental(int n) {
        if (n < 10) {
            return true;
        }
        // n 的位数为 cnt，初始值为 1
        int cnt = 1;
        int tmp = n;
        while (tmp >= 10) {
            tmp /= 10;
            cnt++;
        }
        int next = n % 10;
        for (int i = 0; i < cnt; i++) {
            int num = n % 10;
            n /= 10;
            if (i != 0) {
                if (num > next) {
                    return false;
                } else {
                    next = num;
                }
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//思路2————贪心算法
class Solution {
    public int monotoneIncreasingDigits(int n) {
        if (n < 10) {
            return n;
        }
        //先将 n 转换为字符串，然后再将其转换为字符数组
        char[] chs = String.valueOf(n).toCharArray();
        int length = chs.length;
        //从左往右遍历每一位上的数字，找到第一个开始递减的数字 chs[i]
        int i = 0;
        while (i + 1 < length && chs[i] <= chs[i + 1]) {
            i++;
        }
        if (i == length - 1) {
            //整数 n 本身就是单调递增的，直接返回即可
            return n;
        } else {
            /*
                如果第一个开始递减的数字 chs[i] 的前面还有与其相等的数字，那么需要找到最前面的，
                例如 n = 1444432，chs = ['1', '4', '4', '4', '4', '3', '2']
                那么经过上面的代码可以求出 i = 4，为了找到小于或等于 n 的最大单调递增的数字，
                此时需要往前找到第一个等于 chs[i] 的数字，即 i = 1，然后将 chs[i] 减一，再将
                后面所有的数字置为 9，即可得到 1399999，它即为小于或等于 n 的最大单调递增的数字
            */
            while (i - 1 >= 0 && chs[i - 1] == chs[i]) {
                i--;
            }
            chs[i] = (char) (chs[i] - 1);
            i++;
            while (i < length) {
                chs[i] = '9';
                i++;
            }
        }
        return Integer.parseInt(String.valueOf(chs));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38