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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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());
    }
}