java - 给定一个自然数 N，找出不大于 N 且单调非递减数字的最大数

Question

给定一个非负整数 N，找出小于或等于 N 且单调非递减数字的最大整数。

(回想一下，当且仅当每对相邻数字 x 和 y 满足 x <= y 时，整数才具有单调非递减数字。)

示例 1:输入:N = 10输出:9示例 2:输入:N = 1234输出:1234示例 3:输入:N = 332输出:299注:N为[0, 10^9]范围内的整数。

您好，我正在尝试解决上述问题，如果整数较大，我会超出时间限制。你能告诉我如何优化我的解决方案吗？谢谢。

代码:

class Solution {
        public int monotoneNondecreasingDigits(int N) {

            int num = N;
            int quot=0,rem=0;
            List<Integer> res = new ArrayList<>();

            while( num>=0 ){
               if( checkMontone(num) )
                   res.add(num);
               if( res.size() == 2 ) 
                   break;
                num -= 1;
            }

            return Collections.max(res);
        }

        public boolean checkMontone(int num ){

            String s = Integer.toString(num);

            for( int i=1;i<s.length();i++ ){
                if( (int)s.charAt(i-1) > (int)s.charAt(i) )
                    return false;
            }
            return true;
        }

    }

Answer 1

你不应该使用任何 List因为您可以直接处理号码的数字。

例子

让我们考虑一个数字 776 .这个数字的数字不是单调非递减的 6 < 7 (每个右边的数字不能小于其左边的相邻数字)。

如果我们最大化一个数字 6并减少其相邻的 7然后我们会得到 769 .但它的位数不是单调非递减的。所以，我们应该减少最左边 7并最大化 6和 7 - 699 .

算法

1. 开始从左到右检查您号码的数字。
   1. 如果没有右边的数字小于其左边的相邻数字，那么当前数字就是答案。
   2. 如果某个数字d_i大于其右相邻数字 d_i+1然后递减等于 d_i 的最左边的数字.将该数字后面的所有数字设置为 9 .
2. 打印解决方案

示例代码

private static void printLargestMonoton(String number) {
    char[] chars = number.toCharArray();
    int i = 0;
    // find a position after which the requirement is violated
    while (i < chars.length - 1) {
        if (chars[i] > chars[i + 1]) {
            break;
        }
        i++;
    }

    // if at the end then the number is already the valid one
    if (i == chars.length - 1) {
        System.out.println(String.valueOf(chars));
        return;

    }

    // find the left most position to decrement
    while (i >= 1 && chars[i - 1] == chars[i]) {
        i--;
    }

    // if the leftmost digit is 1 then mark with \0 so that to remove later 
    if (chars[i] == '1') {
        // get rid of this char later to avoid a leading zero
        chars[i] = '\0';
    } else {
        chars[i]--;
    }

    // maximise all the digits to the right of the previous digit
    for (i = i + 1;i < chars.length; i++) {
        chars[i] = '9';
    }

    System.out.println(String.valueOf(chars).replace("\0",""));
}

public static void main(String[] args) {
    String[] numbers = new String[]{"10", "1234", "332", "12214512", "11110"};

    for (String number : numbers) {
        printLargestMonoton(number);
    }
}

输入

19

1234

332

12214512

11110

输出

9

1234

299

11999999

9999