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

待我称王封你为后i 2023-10-06 23:43 39阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

**示例 1：**

输入: n = 10  
输出: 9

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

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

**提示：**  
0 <= n <= 109

来源：力扣（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 的最大单调递增的数字。

## 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;
        }
    }

//思路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));
        }
    }