贪心算法Day06

#738.单调递增的数字

力扣题目链接(opens new window)

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

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

示例 1:

• 输入: N = 10
• 输出: 9

示例 2:

• 输入: N = 1234
• 输出: 1234

示例 3:

• 输入: N = 332
• 输出: 299

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

看到题目的第一想法

? ? ? ? 没思路，不清楚数字要怎么处理

看到代码随想录之后的想法

? ? ? ? 卡哥做法，使用string来处理数字

? ? ? ? 从后往前，看是否递增，找到字符串中第一个递减的位置，把前一个-1 ，后面的全都变成9

? ? ? ? ?

自己实现过程中遇到的困难

? ? 从后往前遍历，如果发现str[i]<str[i-1] 则str[i]--,str[i-1]之后的都赋值为9

? ?使用字符数组处理起来很方便

? ? 记录第一个下标，把后面都置为9

class Solution {
   /*public int monotoneIncreasingDigits(int n) {
        //如果这个数字单调递增的话我们就返回自己
        //如果不单调递增，
        if(isValid(n)){
            return n;
        }

    }
    boolean isValid(int n){
        int s=n;
        while(s!=0){
            if((s/10)%10<=s%10){
                s=s/10;
            }else{
                return false;
            }
        }
        return true;
    }*/
    //卡哥做法 把数字转成string来处理
    //要清楚，要找到最大单调递增的数字，其实就是递减开始第一个数字-1 后面的全为9 比如32->3-1=2 ->29
    //从后往前遍历，如果发现str[i]<str[i-1] 则str[i]--,str[i-1]之后的都赋值为9
    /*public int monotoneIncreasingDigits(int n) {
        StringBuilder s = new StringBuilder(n);
        //从后往前遍历若为递减则记录递减最近的地方
        int flag = s.length();
        for(int i=s.length()-1;i>0;i--){
            if(s.charAt(i-1)>s.charAt(i)){
                //前一个-- 后续都为9
                char t = (char)(s.charAt(i-1)-'1');
                s.setCharAt(i-1,t);
                flag=i;
            }
        }
        for(int i=flag;i<s.length();i++){
            //把后续都置为9
                s.setCharAt(i,'9');
        }
        return Integer.valueOf(s.toString());

    }*/
    public int monotoneIncreasingDigits(int n) {
        String s = n+"";
        char[] c = s.toCharArray();
        //从后往前遍历若为递减则记录递减最近的地方
        int flag = c.length;
        for(int i=c.length-1;i>0;i--){
            if(c[i-1]>c[i]){
                //前一个-- 后续都为9
                c[i-1]--;
                flag=i;
            }
        }
        for(int i=flag;i<c.length;i++){
            //把后续都置为9
                c[i]='9';
        }
        return Integer.parseInt(String.valueOf(c));

    }
}