小于n的最大数

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

示例 1：A={1, 2, 9, 4}，n=2533，返回 2499。

示例 2：A={1, 2, 5, 4}，n=2543，返回 2542。

示例 3：A={1, 2, 5, 4}，n=2541，返回 2525。

示例 4：A={1, 2, 9, 4}，n=2111，返回 1999。

示例 5：A={5, 9}，n=5555，返回 999。

回溯

public class MaxNumber {
    public static int maxNumber(int[] A, int n) {
        char[] nChars = String.valueOf(n).toCharArray();
        Arrays.sort(A);
        List<Integer> digits = new ArrayList<>();
        for (int num : A) {
            digits.add(num);
        }

        int result = findMax(digits, nChars, 0, true, new StringBuilder());

        // 什么时候返回-1？例如n=21，A={2,3}，此时凑不出小于21的两位数（最小是22），所以返回-1。然后用下面的代码找小于2位数的最大数，即3。
        if (result == -1) {
            StringBuilder sb = new StringBuilder();
            int maxDigitInA = digits.get(digits.size() - 1);
            if (maxDigitInA == -1) {
                return -1;
            }
            // 注意这里是nChars.length-1，位数要比n少1。
            for (int i = 0; i < nChars.length - 1; i++) {
                sb.append(maxDigitInA);
            }
            if (sb.length() == 0) {
                return -1;
            }
            return Integer.parseInt(sb.toString());
        }

        return result;
    }

    private static int findMax(List<Integer> digits, char[] nChars, int index, boolean limit, StringBuilder current) {
        if (index == nChars.length) {
            int num = Integer.parseInt(current.toString());
            int target = Integer.parseInt(new String(nChars));
            // 重点。num==target时，不算！必须小于target。
            return num < target ? num : -1;
        }

        int maxDigit = limit ? nChars[index] - '0' : 9;
        int result = -1;

        for (int i = digits.size() - 1; i >= 0; i--) {
            int d = digits.get(i);
            if (d > maxDigit) continue;

            current.append(d);
            int tempResult = findMax(digits, nChars, index + 1, limit && (d == maxDigit), current);
            if (tempResult != -1) {
                result = tempResult;
                break;
            }
            current.deleteCharAt(current.length() - 1);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] A1 = {1, 2, 9, 4};
        int n1 = 2111;
        System.out.println(maxNumber(A1, n1)); // Output: 1999

        int[] A2 = {5, 9};
        int n2 = 5555;
        System.out.println(maxNumber(A2, n2)); // Output: 999

        int[] A3 = {5, 9};
        int n3 = 1000;
        System.out.println(maxNumber(A3, n3)); // Output: 999

        int[] A4 = {1,4,9};
        int n4 = 1000;
        System.out.println(maxNumber(A4, n4));  // Output: 999

        int[] A5 = {2,3};
        int n5 = 21;
        System.out.println(maxNumber(A5, n5));  // Output: 3

        int[] A6 = {2};
        int n6 = 1;
        System.out.println(maxNumber(A6, n6));  // Output: -1
    }
}