贪心---单调递增的数字 Posted on 2021-08-21 00:00:00 2021-08-21 00:00:00 by Author 摘要 给定一个非负整数 N,你能找出小于或等于 N 的最大的整数吗?,同时保证这个整数需要满足其各个位数上的数字是单调递增的. # 单调递增的数字 1. 题目描述 - 给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。) - **提示:**`N` 是在 `[0, 10^9]` 范围内的一个整数。 2. 示例描述 - 示例一 ```java 输入: N = 1234 输出: 1234 ``` - 示例二 ```java 输入: N = 332 输出: 299 ``` 3. 解题思路 - 拿到这道题,首先会想到用暴力解法去做,当然暴力解法可以解决这道题,但是会超时,题目给定的N是一个很大的范围,如果暴力解法一个个去找,肯定会超时的。 - 那么就要想其他方式去解决。首先如果所给定的数字都是单调递增的,那么结果就为该数字。如果该数字不是单调递增是,若要使得数字单调递增并且还要是最大的整数(小于或者等于N),那么这个数从某一位开始后面的每一位上都是9,否则就不能保证这个数是最大的整数(0到N范围内的最大整数),那么怎么找到从某一个位置开始,后续位数都为9尼。 - 这里可以这样想,如果前一个字符大于后一个字符,这就不能保证单调递增,那么前一个字符减一,后一个字符变成9,那么前后两个字符就构成单调递增并且是最大的整数(前后两个字符组成的范围内的最大整数),比如说对于85来说:8大于5,想要找到0到85范围内单调递增并且最大的整数那么可以这样想,8-1=7,5变成9,那么就变成79。79就是0到85范围内最大的并且是单调递增的数字。同理在举个例子543,得到的结果应该是499,那么怎么得到的尼,首先从后向前遍历,4大于3,那么4-1=3,倒数第一个数变成9,对于后两个数43来说,最大单调递增数39,接下来继续看前两个数,5大于3(本来是4,但前一步操作减一了,所以变成了3),那么5-1=4,原来的3变成9,对于53来说,最大的单调递增数位49,那么变化完成后,每个位置上的数字分别位4,9,9。所以对于数字543来说,在0到543范围内最大且单调递增的数字位499。 - 具体代码示例如下,这个需要自己手动实现一下,就会更加深刻的理解其中的原理。 4. 代码示例 ```java public int monotoneIncreasingDigits1(int N) { //标志从第几位开始之后数字都要变成9 //如果所给的数字都是单调递增的,那么flag就没有用了,所有初始为N int flag=N; //把数字转化为字符串,便与后续操作 String s=String.valueOf(N); char[]chars=s.toCharArray(); //从后向前遍历 for(int i=chars.length-1;i>0;i--){ //如果前一个字符大于当前的字符,说明这个不是单调递增的 //我们这是要把其变成最大的数,那么前一个字符减一,后一个数字才能变成9 //这样才能使整个数字单增并且保证数字最大 if(chars[i-1]>chars[i]){ flag=i; chars[i-1]--; } } //找到下标i,之后的数字都变成9,这样才能找到最大数字 for(int i=flag;i<chars.length;i++){ chars[i]='9'; } return Integer.parseInt(new String(chars)); } ```
{{ item.content }}
{{ child.content }}