最大数(给定一个数n如23121；给定一组数字a如[2 4 9]求由a中元素组成的小于n的最大数)

给定一个数n如23121;给定一组数字a如[2 4 9]求由a中元素组成的小于n的最大数

字节面试遇到的,思路其实不难但是最后还是没做出来.主要就是很多的边界条件.从第一位开始进行查询,

• 如果能够在数组中找到等于该位的元素或者能取到小于该位元素的最大值就直接取
• 如果取不到,那么就少一位,以后直接每回都取数组中最大的元素即可

	int ans;
    int value = 23123;
    String str = String.valueOf(value);

    @Test
    public void test1(){
        List list = new ArrayList<>();
        list.add(2);
        list.add(4);
        list.add(9);
        DFS(0,false,0,list);
        System.out.println(ans);
    }

    //pass表示当前位要不要直接跳过
    public boolean DFS(int index,boolean pass,int temp,List list){
        if (index==str.length()){
            ans = temp;
            return true;
        }

        //pass为true的情况,只有最高位没有数，或者上一位数小于对应n中的值
        if(pass){
            return DFS(index+1,true,temp*10+list.get(list.size()-1),list);
        }else{
            int val = str.charAt(index)-'0';

            //找到与这一位相比 取相等的或者小于中最大的一位
            for (int i=list.size()-1;i>=0;i--) {
                //先判断等于这一位的
                if (val==list.get(i)){
                    if (DFS(index+1,false,temp*10+list.get(i),list)){
                        return true;
                    }
                }else if(val>list.get(i)){//要不就取小于这一位的最大值
                    if (DFS(index+1,true,temp*10+list.get(i),list)){
                        return true;
                    }
                }
            }

            //如果该位置都放不了且index!=0
            if (index!=0) return false;
            //如果index==0 上面for循环中这些位置都不满足,应该跳过这一位了
            return DFS(index+1,true,temp,list);
        }
    }