数组A中给定可以使用的1~9的数，返回由A数组中的元素组成的小于n的最大数。例如A={1, 2, 4, 9}，x=2533，返回2499
回溯：从前往后找比自己小的，找不到就回溯。
贪心：永远拼最大数字
用p指针从前往后找跟自己一样大的，找不到就回溯找比自己 减1 一样大的，找到了剩余位置拼最大数。
先分情况：
- {1, 2, 4, 9}，x=2533，-> 2499
- {1, 2, 4, 9}，x=2033，-> 1999
- {1, 2, 4, 9}，x=1033，-> 999
- {1, 2, 4, 9}，x=222202222, -> 222199999
找规律：
用一个p指针从前往后遍历
- 找到一样大的就继续往后找，直到找到比自己小的，比如 2533 直到找到 2499，也就是4比5小，后面直接拼最大数9
- 找不到比自己大的，回溯，比如2033找不到比0小的，就回溯找比（2-1）小的，找到了1，后面直接拼最大数9
所以用p指针从前往后找跟自己一样大的，找不到就回溯找比自己-1一样大的，找到了剩余位置拼最大数。
final static int INIT_FAIL = -10;
public static int getBiggestNum(int[] nums, int target) {
List<Integer> list = new ArrayList<>();
LinkedList<Integer> tmp = new LinkedList<>();
// 从小到大排序
Arrays.sort(nums);
int result = 0;
int t = target;
while (t != 0) {
int num = t % 10;
list.add(num);
t = t / 10;
}
int biggestNum = nums[nums.length - 1];
// 从小到大排序
Collections.reverse(list);
boolean beginBig = false;
// p指针指向当比较的数字
int p = 0;
// 上一次失败的数字，如果存在说明存在匹配失败，p指针正在回溯
int curr = INIT_FAIL;
while (p < list.size()) {
if (beginBig) {
// 可以从p开始拼接最大数了，直到结束
tmp.offerLast(biggestNum);
p++;
} else {
int num = list.get(p);
// 如果curr存在，则查找比curr更小的nearNum，比如curr=2，则查找<=2的数字
int realNum = curr == INIT_FAIL ? num : curr;
int nearNum = getNearNum(nums, realNum);
if (num == nearNum) {
// 相等，则继续往后匹配比较
tmp.offerLast(nearNum);
p++;
} else {
if (nearNum == INIT_FAIL) {
// 没有找到比index=p小的那一位，并且找不到了
if (tmp.isEmpty()) {
// 找到头也没找到直接开始拼接最大数，比如A={1, 2, 4, 9} 1033 -> 999，找不到比10xx小的数字，就拼接0999
tmp.offerLast(0);
beginBig = true;
p++;
} else {
// p回溯，查找上一位
curr = tmp.pollLast() - 1;
p--;
}
} else {
// 找到了比自己小的数字，后面直接开始拼接最大数字就好了，比如A={1, 2, 4, 9}，2533->24xx后直接拼接到2499
beginBig = true;
tmp.offerLast(nearNum);
p++;
}
}
}
}
while (!tmp.isEmpty()) {
int n = tmp.pollFirst();
result = result * 10 + n;
}
return result;
}
