小于n的最大数

题目描述: 数组A中给定可以使用的1~9的数，返回由A数组中的元素组成的小于n（n > 0）的最大数。例如：A = {1, 2, 4, 9}，n = 2533，返回2499。

测试用例:

A = {1, 2, 4, 9}
n = 2533
输出 = 2499 
  
A = {4, 2, 9, 8}
n = 988822
输出 = 988499
  
A = {9, 8}
n = 9
输出 = 8
  
A = {9, 6, 3, 5}
n = 56449
输出 = 56399

思路: 实际上数只有十个,那我们贪心就好了,我们首先匹配这个数 ,如果每一位都在这个数组中存在,就修改最小的一位,如果不就把最高的不能匹配的位之后变成数组中最大值,这一位找一个小的数代替

public class MainTest {
    public static void main(String[] args) {
        System.out.println(maxN(new int[]{1, 2, 4, 9}, 2533));
        System.out.println(maxN(new int[]{4, 2, 9, 8}, 988822));
        System.out.println(maxN(new int[]{9, 8}, 8));
        System.out.println(maxN(new int[]{9, 6, 3, 5}, 56449));
        System.out.println(maxN(new int[]{1,2,3,4,5,6,7,8},8363065));
    }

    // 贪心加二分
    public static int maxN(int[] digits,int n){
        Arrays.sort(digits);
        String str= n + "";
        // 从最高位开始寻找小于等于当前位的数
        boolean less = false;
        int res=0;
        for(int i=0;i<str.length();i++){
            int num = str.charAt(i)-'0';
            if(less) {
                res=res*10+(digits[digits.length-1]);
                continue;
            }
            // 二分寻找小于等于num的第一个数
            int r = binarySearch(digits,num,i<str.length()-1 ? str.charAt(i+1)-'0' : digits[0]);
            // 1. 存在小于当前位的数,后续位之间取最大值
            if(r<num){
                res=res*10 + r;
                less=true;
            }
            // 2. 存在等于当前位的数,继续寻找小于后续位的数
            else if(r==num){
                res=res*10 + r;
            }
            // 3. 不存在小于当前位的数,返回-1
            else return -1;
        }
        return res;
    }

    // 返回小于等于target的第一个数
    public static int binarySearch(int[] digits,int target,int next){
        // 如果下一个数比digits数组中任何一个数都要小,那么当前target只能找小于的数,不能找等于的数
        if(next<digits[0]) target--;
        int b=0,e=digits.length-1;
        while(b<=e){
            int m=(b+e)>>1;
            if(e-b<=1){
                if(digits[e]<=target) return digits[e];
                if(digits[b]<=target) return digits[b];
                return digits[b];
            }else if(digits[m]==target) return target;
            else if(digits[m]>target) e=m-1;
            else b=m;
        }
        return digits[b];
    }
}