小于n的最大数，记一道字节面试题

package client;

import java.util.Arrays;

public class MainTest {
    public static void main(String[] args) {
        // Test case examples
        System.out.println(maxN(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 235)); // Expected: 235
        System.out.println(maxN(new int[]{0, 2, 4, 6, 8}, 357)); // Expected: 288
        System.out.println(maxN(new int[]{1, 2, 3}, 987654)); // Expected: 333333
        System.out.println(maxN(new int[]{1}, 1111)); // Expected: 1111
        System.out.println(maxN(new int[]{1, 3, 5, 7, 9}, 2468)); // Expected: 1999
        System.out.println(maxN(new int[]{1, 2, 3, 4, 5}, 654)); // Expected: 555
        System.out.println(maxN(new int[]{3, 5, 8}, 572)); // Expected: 558
        System.out.println(maxN(new int[]{2, 3}, 100)); // Expected: 33
        System.out.println(maxN(new int[]{5}, 123)); // Expected: 55
        System.out.println(maxN(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 0)); // Expected: 0
        System.out.println(maxN(new int[]{2,4,9},23121));// Expected: 22999
    }

    private static String result = null;

    public static int maxN(int[] digits, int n) {
        Arrays.sort(digits);
        result = null;
        dfs(digits, String.valueOf(n), new StringBuilder(), 0, true);
        return Integer.parseInt(result);
    }

    private static void dfs(int[] digits, String target, StringBuilder current, int index, boolean isLimit) {
        if (result != null) {
            return;
        }
        if (index == target.length()) {
            result = current.toString();
            return;
        }

        if (!isLimit) {
            current.append(digits[digits.length - 1]);
            dfs(digits, target, current, index + 1, false);
        } else {
            boolean hasValidDigit = false;
            int limit = target.charAt(index) - '0';
            for (int i = digits.length - 1; i >= 0; i--) {
                if (digits[i] <= limit) {
                    hasValidDigit = true;
                    current.append(digits[i]);
                    dfs(digits, target, current, index + 1, digits[i] == limit);
                    current.deleteCharAt(current.length() - 1);
                }
            }
            if (!hasValidDigit) {
                dfs(digits, target, current, index + 1, false);
            }
        }
    }
}