738.单调自增的数字

小鱼儿 2023-10-16 15:43 13阅读 0赞

#### 738.单调自增的数字 ####

*  题干分析
 *  贪心算法解题
 *  总结
 *  代码实现
 *   *  1. 创建String数组并多次使用Integer.parseInt方法的解法
     *  2. 在char数组上原地修改的解法

## 题干分析 ##

[力扣入口][Link 1]

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

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

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

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

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

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

## 贪心算法解题 ##

题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。

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

这一点如果想清楚了，这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢？

从前向后遍历的话，遇到strNum\[i - 1\] > strNum\[i\]的情况，让strNum\[i - 1\]减一，但此时如果strNum\[i - 1\]减一了，可能又小于strNum\[i - 2\]。

这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。

## 总结 ##

本题只要想清楚个例，例如98，一旦出现strNum\[i - 1\] > strNum\[i\]的情况（非单调递增），首先想让strNum\[i - 1\]减一，strNum\[i\]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。

想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。

最后代码实现的时候，也需要一些技巧，例如用一个flag来标记从哪里开始赋值9。

## 代码实现 ##

### 1. 创建String数组并多次使用Integer.parseInt方法的解法 ###

class Solution {
        
       // 738. 单调递增的数字
        public int monotoneIncreasingDigits(int N){
        
            String[] strings = (N + "").split("");
            int start = strings.length;
            for(int i = strings.length - 1; i > 0; i--){
        
                if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
        
                    strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                    start = i;
                }
            }
            for(int i = start; i < strings.length; i++){
        
                strings[i] = "9";
            }
            return Integer.parseInt(String.join("",strings));
        }
    }

### 2. 在char数组上原地修改的解法 ###

class Solution {
        
       // 738. 单调递增的数字 - char数组上原地修改
        public int monotoneIncreasingDigits(int n){
        
            String s = String.valueOf(n);
            char[] chars = s.toCharArray();
            int start = s.length();
            for(int i = s.length() - 2; i >= 0;i--){
        
                if(chars[i] > chars[i+1]){
        
                    chars[i]--;
                    start = i+1;
                }
            }
            for(int i = start; i < s.length(); i++){
        
                chars[i] = '9';
            }
            return Integer.parseInt(String.valueOf(chars));
        }
    }

**参考资料**：[代码随想录-738.单调递增的数字][-738.]

[Link 1]: https://leetcode.cn/problems/monotone-increasing-digits/
[-738.]: https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE