贪心---单调递增的数字 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 }}