时间戳

首页 > 解决方案 > 给定一个自然数 N，找出不大于 N 且单调非减数的最大数

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

问题描述

给定一个非负整数 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;
        }

    }

标签： javaalgorithmdata-structures

解决方案

您不应该使用任何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

推荐阅读