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

63 阅读 0 评论 42 点赞

我是靠谱客的博主冷傲可乐，最近开发中收集的这篇文章主要介绍给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

这里本人写出了两种解决方案----

第一种:效率较低-- 循环N-- 直到符合要求的数出现


import java.util.Arrays;


public class Test {
    public static void main(String[] args) {
        int N = 549776;
        long t=System.currentTimeMillis();
        String m;
        int k;
        String[] l;
        while (N > 1) {
            int i = 0;
            k = Integer.toString(N).length();
            m = Integer.toString(N);
            l = m.split("");
            for (; i < k - 1; i++) {
                if (Integer.valueOf(l[i]) > Integer.valueOf(l[i + 1])) {
                    i = -1;
                    break;
                }
            }
            if (i == k - 1) {
                Arrays.stream(l).forEach(System.out::print);
                break;
            }
            N--;
        }
        System.out.println();
        System.out.println(System.currentTimeMillis()-t);
    }
}

第二种:判断N的第i位是否比第i+1位大 ,若大则第i位-1 剩余位赋值9,然后递归N直到符合要求

package jvm;

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

//与上一代码相比 优化不少----
public class Test5_1 {
    public static void main(String[] args) {
        int N = 332;
        long t = System.currentTimeMillis();
        System.out.println(wqe(N));
        System.out.println(System.currentTimeMillis() - t);
    }

    //将数字变成 数组 便于处理
    private static int wqe(int n) {
        String m = Integer.toString(n);
        String[] l = m.split("");
        if (n > 1) {
            return qqq(del(m.length(), l.length, l));
        }
        return 1;
    }

    //递归数组 直到第i位比第i-1位小
    private static String[] del(int k, int k2, String[] l) {
        for (int i = 0; i < k - 1; i++) {
            if (Integer.valueOf(l[i]) > Integer.valueOf(l[i + 1])) {
                l[i] = Integer.toString(Integer.valueOf(l[i]) - 1);
                for (;i + 1 < k2;i++) {
                    l[i + 1] = Integer.toString(9);
                }
                del(k, k2, l);
            }
        }
        return l;
    }

    //将数组转变为 数字
    private static int qqq(String[] l) {
        StringBuilder result = new StringBuilder();
        for (String s : l) {
            result.append(s);
        }
        return Integer.valueOf(result.toString());
    }
}