字节一面笔试题：小于n的最大数

指定降序数组arr和数字n，输出数组能组成的小于等于数字n的最大值。比如arr=[9,4,3,2],n=433211,输出432999；

思路，贪心+二分。

难的在于中途有数字找不到比它小的数的话，得回退，需要确认回退逻辑怎么写。

Java代码如下：

public int maxNum(){

List<Integer> arr = Arrays.asList(9,4,3,2);

int n = 433211;

List<Integer> nlist = new ArrayList<>();

int base = 0;

while(n!=0){

nlist.add(0,n%10);

n /= 10;

base = base*10+1;

}

boolean less = false;

int res = 0;

for(int i=0;i<nlist.size();i++){

if(less){

res = res*10+arr.get(0);

continue;

}

int index = find(arr,nlist.get(i));

if(index==-1){

int l = i;

while(l>=0&&index==-1){

index = find(arr,nlist.get(l)-1);

l-=1;

}

if(index==-1){

res = base*arr.get(0)/10;

break;

}

res = res/((int) Math.pow(10,i-l-1));

res = res*10 + nlist.get(index);

for(int p=0;p<i-l-1;p++){

res = res*10+arr.get(0);

}

less = true;

}else if(arr.get(index)==nlist.get(i)){

res = res*10+arr.get(index);

}else{

res = res*10+arr.get(index);

less = true;

}

}

return res;

}

public int find(List<Integer> arr,int k){

if(k<arr.get(arr.size()-1)) return -1;

int index = -1;

int l = 0,r = arr.size()-1;

while(l<=r){

int mid = (l+r)/2;

if(arr.get(mid)==k){

return mid;

}else if(arr.get(mid)<k){

index = mid;

r = mid -1;

}else{

l = mid + 1;

}

}

return index;

}