题目描述

数组nums中给定可以使用的1~9的数，返回由数组nums中的元素组成的小于n的最大数。

示例 1：

1
2
输入：nums = {1, 2, 9, 4}，n = 2533
输出：2499

示例 2：

1
2
输入：nums = {1, 2, 5, 4}，n = 2543
输出：2542

示例 3：

1
2
输入：nums = {1, 2, 5, 4}，n = 2541
输出：2525

示例 4：

1
2
输入：nums = {1, 2, 9, 4}，n = 2111
输出：1999

示例 5：

1
2
输入：nums = {5, 9}，n = 5555
输出：999

示例 6：

1
2
输入：nums = {5, 9}，n = 3
输出：-1

我的解法

思路

  1. 对每一位先尝试使用相同数字
  2. 如果没有相同数字，判断是否存在比当前数字更小的数字，如果有，则选择更小数字中的最大数，剩余的数字用最大数字
  3. 如果没有，向前查找前一个数字有没有更小的数字
  4. 直到回溯到第一个数字，就用位数更少但全部都是最大的数

代码

在实际代码编写中我们添加一个标志末尾字符，当遍历到此字符时必定会向前查找，统一因缺少数字与所有数字都包含的情况，例如：

  1. 缺少数字
1
2
输入：nums = {1, 2, 9, 4}，n = 2533
输出：2499

2533遍历到第一个3时，因为nums数组中不存在3，因此需要向前一位查找更小的数字

  1. 所有数字都包含
1
2
输入：nums = {1, 2, 9, 4}，n = 2111
输出：1999

2111遍历完毕，所有的数字都包含，最后结果为2111，因此需要再向前一位查找更小的数字

添加一个标志末尾字符的目的就是统一以上两种情况，避免重复编码，值得注意的是添加的标志字符的ASCII码值应小于’0’，必须使set.lower(num)返回为null。

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
class Solution {

    public int getMaxNumBelowN(int[] nums, int n) {
        TreeSet<Integer> set = new TreeSet<>();
        Arrays.stream(nums).forEach(set::add);
        StringBuilder result = new StringBuilder();
        int max = Arrays.stream(nums).max().getAsInt();
        StringBuilder s = new StringBuilder(String.valueOf(n)).append('!');
        for (int i = 0; i < s.length(); i++) {
            int num1 = s.charAt(i) - '0';
            result.append(s.charAt(i));
            if (!set.contains(num1)) {
                // 从当前位置向前查找
                for (int j = result.length() - 1; j >= 0; j--) {
                    int num = result.charAt(j) - '0';
                    result.deleteCharAt(j);
                    Integer lower = set.lower(num);
                    if (lower != null) {
                        result.append(lower);
                        while (result.length() < s.length() - 1) {
                            result.append(max);
                        }
                        return Integer.parseInt(result.toString());
                    }
                }
                // 不存在小于n的最大数
                int length = s.length() - 2;
                if (length == 0) {
                    return -1;
                }
                // 向前未找到小于n的最大数
                return Integer.parseInt(String.valueOf(max).repeat(length));
            }
        }
        return -1;
    }

}

测试

添加测试用例：

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
class Test {
    int[] nums;
    int n;
    int expect;

    public Test(int[] nums, int n, int expect) {
        this.nums = nums;
        this.n = n;
        this.expect = expect;
    }
}

public class Main {

    public static void main(String[] args) {
        Solution solution = new Solution();
        Test[] testList = new Test[]{
                new Test(new int[]{1, 2, 9, 4}, 2533, 2499),
                new Test(new int[]{1, 2, 5, 4}, 2543, 2542),
                new Test(new int[]{1, 2, 5, 4}, 2541, 2525),
                new Test(new int[]{1, 2, 9, 4}, 2111, 1999),
                new Test(new int[]{1, 2, 9, 4}, 1111, 999),
                new Test(new int[]{5, 9}, 5555, 999),
                new Test(new int[]{5, 9}, 33, 9),
                new Test(new int[]{5, 9}, 3, -1),
                new Test(new int[]{5, 9, 7}, 9, 7),
                new Test(new int[]{6, 7, 8}, 1200, 888),
                new Test(new int[]{1, 2, 4, 9}, 4921, 4919),
        };
        for (Test test : testList) {
            int maxNumBelowN = solution.getMaxNumBelowN(test.nums, test.n);
            System.out.println((maxNumBelowN == test.expect) + "------>" + maxNumBelowN);
        }
    }

}

运行启动类，查看控制台：

1
2
3
4
5
6
7
8
9
10
true------>2542
true------>2525
true------>1999
true------>999
true------>999
true------>9
true------>-1
true------>7
true------>888
true------>4919