题目

Leetcode 738：
给定一个非负整数N，找出小于或等于N的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字x和y满足x <= y时，我们称这个整数是单调递增的。）

例如：
N = 352，则满足的整数结果为：349

思路一

分离每个位置的数字，将其转化为字符类型进行逐位比较

代码

/**
 * @author Seaguller
 * @date 2021/7/19 09:35
 * @Description
 */
public class FirstMethod {

    /**
     * 给定一个非负整数N，找出小于或等于N的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
     * （当且仅当每个相邻位数上的数字x和y满足x <= y时，我们称这个整数是单调递增的。）
     *
     * 思路：分离每个位置的数字，将其转化为字符类型进行逐位比较
     * 结果：超出时间限制
     */
    public int monotoneIncreasingDigits(int n) {

        int resultNum = n;
        while(!judgeNumRise(resultNum)) {
            resultNum --;
        }

        return resultNum;
    }

    /**
     * 判断某整数各个位数上的数字是否为单调递增
     * @param num 整数
     * @return 判断是/否
     */
    private boolean judgeNumRise(int num) {

        String numStr = String.valueOf(num);
        int numLen = numStr.length();

        for(int i=0; i<numLen-1; i++) {
            char preChar = numStr.charAt(i);
            char nextChar = numStr.charAt(i+1);

            if(nextChar < preChar) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        FirstMethod solution = new FirstMethod();
        int num = solution.monotoneIncreasingDigits(99999998);
        System.out.println(num);
    }
}

结果超出时间限制（暴力破解法时间过长）

思路二

贪心算法，从后往前依次比较，记录递减开始位置，将该位置数字减1（注意减1后前面仍为递增数列），其后设为9

代码

/**
 * @author Seaguller
 * @date 2021/7/19 09:50
 * @Description
 */
public class SecondMethod {

    /**
     * 给定一个非负整数N，找出小于或等于N的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
     * （当且仅当每个相邻位数上的数字x和y满足x <= y时，我们称这个整数是单调递增的。）
     *
     * 思路：贪心算法，从后往前依次比较，记录递减开始位置，将该位置数字减1（注意减1后前面仍为递增数列），其后设为9
     * 结果：通过
     */
    public int monotoneIncreasingDigits(int n) {
        String numStr = String.valueOf(n);
        int numLen = numStr.length();

        if(numLen == 1) {
            return n;
        }

        int index = numLen - 1;
        char cIdx = numStr.charAt(numLen-1);
        for(int i=numLen-2; i>=0; i--) {

            char preNum = numStr.charAt(i);

            if(cIdx < preNum) {
                index = i;
                cIdx = intToChar(charToInt(preNum) - 1);
            } else {
                cIdx = preNum;
            }

        }

        if(index == numLen-1) {
            return n;
        }

        int multiple = 1;
        int resultNum = 0;
        for(int i=numLen-1; i>=0; i--) {
            if(i > index) {
                resultNum += 9 * multiple;
            } else if(i == index) {
                int numIndex = charToInt(numStr.charAt(i)) - 1;
                resultNum += numIndex * multiple;
            } else {
                int numIndex = charToInt(numStr.charAt(i));
                resultNum += numIndex * multiple;
            }

            multiple *= 10;
        }

        return resultNum;

    }

    /**
     * char转换为int
     * @param c 字符
     * @return 整数
     */
    private int charToInt(char c) {
        return c - '0';
    }

    /**
     * int转换为char
     * @param n 整数
     * @return 字符
     */
    private char intToChar(int n) {
        return (char) (n + '0');
    }

    public static void main(String[] args) {
        SecondMethod solution = new SecondMethod();
        int num = solution.monotoneIncreasingDigits(418915689);
        System.out.println(num);
    }

}