给定一个数字字符串N和一个数组nums，数组中的元素都在0~9之间，问从数组中选择元素组成的数字，小于N的最大值是多少？
例如：N = “24378”，nums:{2,3,9}，组成的最大值为23999。

👨‍🏫 参考视频

🍻 code

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        /*
        示例 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。
         */

        // 示例1
        int[] a1 = {1, 2, 9, 4};
        int n1 = 2533 ;
        System.out.println("示例1：" +Arrays.toString(a1)+"," + n1 + " : "+ getMaxLessNum(a1, n1) + " (应返回2499)");

        // 示例2
        int[] a2 = {1, 2, 5, 4};
        int n2 = 2543;
        System.out.println("示例2：" +Arrays.toString(a2)+"," + n2 + " : "+ getMaxLessNum(a2, n2) + " (应返回2542)");

        // 示例3
        int[] a3 = {1, 2, 5, 4};
        int n3 = 2541;
        int m = 2541;

        System.out.println("示例3：" +Arrays.toString(a3)+"," + n3 + " : "+ getMaxLessNum(a3, n3) + " (应返回2525)");

        // 示例4
        int[] a4 = {1, 2, 9, 4};
        int n4 = 2111;
        System.out.println("示例4：" +Arrays.toString(a4)+"," + n4 + " : "+ getMaxLessNum(a4, n4) + " (应返回1999)");

        // 示例5
        int[] a5 = {5, 9};
        int n5 = 5555 ;
        System.out.println("示例5：" +Arrays.toString(a5)+"," + n5 + " : " + getMaxLessNum(a5, n5) + " (应返回999)");

        int[] a6 = {5};
        int n6 = 2 ;
        System.out.println("示例6：" +Arrays.toString(a6)+"," + n6 + " : "+ getMaxLessNum(a6, n6) + " (不存在)");
    }

    static int[] nums;

    /**
     * 获取由数组nums中的元素组成的数字，且小于n的最大值
     */
    public static String getMaxLessNum(int[] a, int b) {
        // 对nums数组进行排序，方便后续查找最大值
        nums = a;
        Arrays.sort(nums);
        int[] n = String.valueOf(b).chars().map(c -> c - '0').toArray();
        // 用于存储结果数字的字符串
        // 深度优先搜索，寻找最大值
        StringBuilder ans = new StringBuilder();
        dfs(true, ans,n, 0);

        return ans.length() == 0 ? "不存在" :ans.toString();
    }
 
    /**
     * 深度优先搜索，寻找最大值
     * @param equal：
     *              true 表示前面的都相等
     *              false 表示前面有小于 nums 的位后面都可以取最大
     * @param n 表示的是最大数
     * @param idx 表示最大数枚举到的下标
     */
    private static boolean dfs(boolean equal, StringBuilder ans, int[] n,  int idx) {
        // 如果是最后一位，则需要判定是否有小于n的数
        if (idx == n.length - 1) {
            if (!equal) {
                // 如果前面已经有不相等的位，则直接取nums的最大值
                ans.append(nums[nums.length - 1]);
                return true;
            } else { // 说明前面的数位都相等，当前数位必须取一个小于 n 对应数位的值，找不到返回 false
                // 否则需要寻找小于n最后一位的最大值
                for (int i = nums.length - 1; i >= 0; i--) {
                    if (nums[i] < n[n.length - 1]) {
                        ans.append(nums[i]);
                        return true;
                    }
                }
                return false;
            }
        }

        // 前面有不相等的，后面都取nums的最大值即可
        if (!equal) {
            for (int i = idx; i < n.length; i++) {
                ans.append(nums[nums.length - 1]);
            }
            return true;
        }

        // 前面都相等，优先取和n[idx]相同的值(因为高位大才是真的大)，深度优先遍历，如果后面组成的数小于n，则找到了最大的值。
        // 如果当前值小于n[idx]，则后面都取nums的最大值即可
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == n[idx]) {
                ans.append(nums[i]);
                boolean result = dfs(true,ans, n, idx + 1);
                if (result) {
                    return true;
                } else {
                    ans.deleteCharAt(ans.length() - 1); // 回溯，删除最后一个字符
                }
            }

            if (nums[i] < n[idx]) {
                ans.append(nums[i]);
                dfs(false,ans, n, idx + 1); // 后续位都取最大值
                return true;
            }
        }

        // 神之一笔，所有都不满足，直接取减少一位
        // 如果前面都不满足，删除第一位即可
        if (idx == 0) {
            dfs(false,ans,  n, idx + 1);
            return true;
        }

        return false;
    }
}

👨‍🏫 参考博客

🍻 code 二刷

import java.util.Arrays;

public class 小于n的最大数
{

	static int[] nums;

	/**
	 * 获取由数组nums中的元素组成的数字，且小于n的最大值
	 */
	public static String getMaxLessNum(int[] a, int b)
	{
		// 对nums数组进行排序，方便后续查找最大值
		nums = a;
		Arrays.sort(nums);
		String target = String.valueOf(b);
		StringBuilder cur = new StringBuilder();
		boolean res = dfs(true, cur, target, 0);
		if (res)
		{
			return cur.toString();
		}
		String ans = "";
		for (int i = 0; i < target.length() - 1; i++)
		{
			ans += nums[nums.length - 1];
		}
		return ans.equals("") ? "不存在" : ans;
	}

	/**
	 *
	 * @param flag   表示高位是否完全匹配
	 * @param cur
	 * @param target
	 * @param idx
	 * @return
	 */
	private static boolean dfs(boolean flag, StringBuilder cur, String target, int idx)
	{
		if (cur.length() != 0 && idx == target.length())
		{
			int x = Integer.parseInt(cur.toString());
			int y = Integer.parseInt(target);
			if (x < y)
			{
				return true;
			}
			return false;
		}
		int y = target.charAt(idx) - '0';
		// 高位不匹配的情况，剩下的低位都可以取最大值
		if (!flag)
		{
			cur.append(nums[nums.length - 1]);
			boolean res = dfs(flag, cur, target, idx + 1);
			if (res)
			{
				return true;
			} else
			{
				return false;
			}
		}
		// 贪心优先选择最大值
		int curMax = flag ? y : 10;
		for (int i = nums.length - 1; i >= 0; i--)
		{
			int x = nums[i];
			if (x <= curMax)
			{
				boolean newFlag = !(x < y);
				cur.append(x);
				boolean res = dfs(newFlag, cur, target, idx + 1);
				if (res)
				{
					return true;
				}
				// 恢复现场
				cur.deleteCharAt(cur.length() - 1);
			}
		}
		return false;
	}

	public static void main(String[] args)
	{
		/*
		示例 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。
		
		示例 6：A={5}，n=2，返回 不存在。
		 */

		// 示例1
		int[] a1 = { 1, 2, 9, 4 };
		int n1 = 2533;
		System.out.println("示例1：" + Arrays.toString(a1) + "," + n1 + " : " + getMaxLessNum(a1, n1) + " (应返回2499)");

		// 示例2
		int[] a2 = { 1, 2, 5, 4 };
		int n2 = 2543;
		System.out.println("示例2：" + Arrays.toString(a2) + "," + n2 + " : " + getMaxLessNum(a2, n2) + " (应返回2542)");

		// 示例3
		int[] a3 = { 1, 2, 5, 4 };
		int n3 = 2541;
		int m = 2541;

		System.out.println("示例3：" + Arrays.toString(a3) + "," + n3 + " : " + getMaxLessNum(a3, n3) + " (应返回2525)");

		// 示例4
		int[] a4 = { 1, 2, 9, 4 };
		int n4 = 2111;
		System.out.println("示例4：" + Arrays.toString(a4) + "," + n4 + " : " + getMaxLessNum(a4, n4) + " (应返回1999)");

		// 示例5
		int[] a5 = { 5, 9 };
		int n5 = 5555;
		System.out.println("示例5：" + Arrays.toString(a5) + "," + n5 + " : " + getMaxLessNum(a5, n5) + " (应返回999)");

		int[] a6 = { 5 };
		int n6 = 2;
		System.out.println("示例6：" + Arrays.toString(a6) + "," + n6 + " : " + getMaxLessNum(a6, n6) + " (不存在)");
	}

}