字节高频题 小于n的最大数

题目要求：给定一个数n和一个集合s/数组nums，求用集合/数组中的元素组成的小于n的最大整数。集合s中的元素可以重复选取。举例：给一个数n = 333和一个集合s = {2,5,9}，求用s组成的小于n的最大数，那么这里答案应该为299。

1.思路：贪心 + 回溯（带二分查找优化）。

（1）贪心选择：贪心算法适合处理这种数字可重复使用的不可重复选择问题。在从左到右的选择过程中，一旦在某个位置选择了小于n对应位的数字，后面所有位的数字都要取允许集合中的最大值，这样求得的结果就一定是在该前缀下的最大的。

（2）回溯保证全局最优：如果某一位找不到 <= 原数字的允许数字，说明这条路径不可行，必须减小前一位。回溯过程要保持结果仍然是“小于n的最大数”。

（3）如果没有办法构造一个和n的位数相同、但值小于n的数字，那么就退一步，构造一个比n少一位，且每一位都取允许集合中的最大数字的数。也就是在“位数更少”的前提下能得到的最大值。

2.举例说明：

（1）示例1：n = 333，允许数字 = {2，5，9}。

过程：第一位要找 <= 3的最大允许数字 -> 最大是2，并且2 < 3，所以第一位直接选2，后面直接全部选允许集合中的最大值， 得到299 < 333，成功。这种情况属于长度相同且构造成功，不需要减少长度。

（2）示例2：n = 1000，允许数字 = {9}。

过程：第一位要找 <= 1的最大允许数字 -> 允许数字只有9，9 > 1，没有数字可用。考虑回溯，但是无法通过减少任何一位（整串全是9都大于1000的任何前缀），说明长度相同的数不可能构造出来。于是退而求其次，返回3位（比n少一位）的最大数999。999就是所有位数 < 4的数中最大的，这种情况属于长度不同且构造成功。

3.复杂度分析：

（1）时间复杂度：O(L*logD)，其中L为n的位数，D为负责构造结果的允许的数字种类数。由于允许数字种类数D <= 10，因此因此时间复杂度也可视为O(L)。

（2）空间复杂度：O(L)，只存储结果字符串。

附代码：

class Solution { public String maxLessThanN(String n, int[] digits) { char[] chars = n.toCharArray(); int len = chars.length; char[] result = new char[len]; // 对允许使用的数字从小到大排序 int[] sorted = digits.clone(); Arrays.sort(sorted); // 贪心 + 回溯 for (int i = 0; i < len; i++) { // 把当前位记作curDigit int curDigit = chars[i] - '0'; // 二分查找允许使用的数字中 <= curDigit的最大允许数字 int idx = searchLastLessOrEqual(sorted, curDigit); // idx = -1表示没找到 // 即允许使用的数字中没有 <= curDigit的最大允许数字 // 需要回溯 if (idx == -1) { // found置为false，表示没找到 boolean found = false; for (int j = i - 1; j >= 0; j--) { // 从当前位的上一位开始往前遍历，每一位记作prevDigit // 从当前位的上一位开始依次往前找，二分查找允许使用的数字中 < prevDigit的最大允许数字 int prevDigit = result[j] - '0'; int prevIdx = searchLastLess(sorted, prevDigit); // 往前遍历的过程中在某一位找到了 < prevDigit的最大允许数字 if (prevIdx >= 0) { // 回溯成功，把找到的j位置为 < prevDigit的最大允许数字 result[j] = (char) (sorted[prevIdx] + '0'); // 把结果数组res中 < prevDigit的最大允许数字后的数字全部置为sorted数组中的最大数字 fillMaxFrom(j + 1, result, sorted); // 回溯成功，found更新为true found = true; // 后位全部提前补全，因此提前退出（只有回溯失败会走完回溯倒退遍历for循环，节省了时间） break; } } // 如果回溯成功，返回res数组 if (found) { return new String(result); } else { // 回溯失败，i位的前面的位中每一位都无法缩小 // 说明长度相同的数已不可能构造出结果 // 返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } } // 走到这说明没有提前return // 说明前面的代码执行很顺利，没有走回溯逻辑 // 说明二分查找能找到允许使用的数字中 <= curDigit的最大允许数字 // 拿到要找的数chosen，即允许使用的数字中 <= curDigit的最大允许数字 // 把结果数组res中当前位置i置为chosen int chosen = sorted[idx]; result[i] = (char) (chosen + '0'); // 如果拿到的chosen是小于curDigit的，而非等于 // 那么后面的数字全部置为sorted数组中的最大数字，return 结果 即可 if (chosen < curDigit) { fillMaxFrom(i + 1, result, sorted); return new String(result); } } // 走到这还没return，说明完全匹配，前面每一位都是chose = curDigit // 那么说明res == n，允许使用的数字完全可以构成n // 但是题目要求是小于 for (int j = len - 1; j >= 0; j--) { // 从当前位开始往前遍历，去找允许使用的数字中 < 当前位curDigit的最大允许数字 int curDigit = result[j] - '0'; int idx = searchLastLess(sorted, curDigit); // 如果能找到 if (idx >= 0) { // 把该位置为 < 该位curDight的最大允许数字 result[j] = (char) (sorted[idx] + '0'); // 并把该位后面的位全部置为sorted数组中的最大数字，return 结果 即可 fillMaxFrom(j + 1, result, sorted); return new String(result); } } // 如果每一位都无法缩小，那么也要返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } // 寻找 <= target的最大索引位置 private int searchLastLessOrEqual(int[] sorted, int target) { int left = 0, right = sorted.length - 1; // 默认值-1表示没找到 int idx = -1; while (left <= right) { int mid = (left + right) / 2; if (sorted[mid] <= target) { // 每次找到一个合格的值就记录它，但不立刻返回 // 不断二分缩小区间 idx = mid; // left继续向右找，看有没有更大的合格值 left = mid + 1; } else { right = mid - 1; } } return idx; } // 寻找 < target的最大索引位置 private int searchLastLess(int[] sorted, int target) { int left = 0, right = sorted.length - 1; // 默认值-1表示没找到 int idx = -1; while (left <= right) { int mid = (left + right) / 2; if (sorted[mid] < target) { // 每次找到一个合格的值就记录它，但不立刻返回 // 不断二分缩小区间 idx = mid; // left继续向右找，看有没有更大的合格的值 left = mid + 1; } else { right = mid - 1; } } return idx; } // 把start及后面的位全部置为sorted数组中的最后一个元素值（最大值） private void fillMaxFrom(int start, char[] result, int[] sorted) { int maxDigit = sorted[sorted.length - 1]; for (int i = start; i < result.length; i++) { result[i] = (char) (maxDigit + '0'); } } // 构建长度为len的全部由sorted数组的最后一位组成的数组（此处的len即为n的长度len - 1） private String buildAllMax(int len, int[] sorted) { if (len <= 0) return ""; int maxDigit = sorted[sorted.length - 1]; char[] res = new char[len]; Arrays.fill(res, (char) (maxDigit + '0')); return new String(res); } }

ACM模式：

import java.util.Scanner; import java.util.Arrays; class Solution { public String maxLessThanN(String n, int[] digits) { char[] chars = n.toCharArray(); int len = chars.length; char[] result = new char[len]; // 对允许使用的数字从小到大排序 int[] sorted = digits.clone(); Arrays.sort(sorted); // 贪心 + 回溯 for (int i = 0; i < len; i++) { // 把当前位记作curDigit int curDigit = chars[i] - '0'; // 二分查找允许使用的数字中 <= curDigit的最大允许数字 int idx = searchLastLessOrEqual(sorted, curDigit); // idx = -1表示没找到 // 即允许使用的数字中没有 <= curDigit的最大允许数字 // 需要回溯 if (idx == -1) { // found置为false，表示没找到 boolean found = false; for (int j = i - 1; j >= 0; j--) { // 从当前位的上一位开始往前遍历，每一位记作prevDigit // 从当前位的上一位开始依次往前找，二分查找允许使用的数字中 < prevDigit的最大允许数字 int prevDigit = result[j] - '0'; int prevIdx = searchLastLess(sorted, prevDigit); // 往前遍历的过程中在某一位找到了 < prevDigit的最大允许数字 if (prevIdx >= 0) { // 回溯成功，把找到的j位置为 < prevDigit的最大允许数字 result[j] = (char) (sorted[prevIdx] + '0'); // 把结果数组res中 < prevDigit的最大允许数字后的数字全部置为sorted数组中的最大数字 fillMaxFrom(j + 1, result, sorted); // 回溯成功，found更新为true found = true; // 后位全部提前补全，因此提前退出（只有回溯失败会走完回溯倒退遍历for循环，节省了时间） break; } } // 如果回溯成功，返回res数组 if (found) { return new String(result); } else { // 回溯失败，i位的前面的位中每一位都无法缩小 // 说明长度相同的数已不可能构造出结果 // 返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } } // 走到这说明没有提前return // 说明前面的代码执行很顺利，没有走回溯逻辑 // 说明二分查找能找到允许使用的数字中 <= curDigit的最大允许数字 // 拿到要找的数chosen，即允许使用的数字中 <= curDigit的最大允许数字 // 把结果数组res中当前位置i置为chosen int chosen = sorted[idx]; result[i] = (char) (chosen + '0'); // 如果拿到的chosen是小于curDigit的，而非等于 // 那么后面的数字全部置为sorted数组中的最大数字，return 结果 即可 if (chosen < curDigit) { fillMaxFrom(i + 1, result, sorted); return new String(result); } } // 走到这还没return，说明完全匹配，前面每一位都是chose = curDigit // 那么说明res == n，允许使用的数字完全可以构成n // 但是题目要求是小于 for (int j = len - 1; j >= 0; j--) { // 从当前位开始往前遍历，去找允许使用的数字中 < 当前位curDigit的最大允许数字 int curDigit = result[j] - '0'; int idx = searchLastLess(sorted, curDigit); // 如果能找到 if (idx >= 0) { // 把该位置为 < 该位curDight的最大允许数字 result[j] = (char) (sorted[idx] + '0'); // 并把该位后面的位全部置为sorted数组中的最大数字，return 结果 即可 fillMaxFrom(j + 1, result, sorted); return new String(result); } } // 如果每一位都无法缩小，那么也要返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } // 寻找 <= target的最大索引位置 private int searchLastLessOrEqual(int[] sorted, int target) { int left = 0, right = sorted.length - 1; // 默认值-1表示没找到 int idx = -1; while (left <= right) { int mid = (left + right) / 2; if (sorted[mid] <= target) { // 每次找到一个合格的值就记录它，但不立刻返回 // 不断二分缩小区间 idx = mid; // left继续向右找，看有没有更大的合格值 left = mid + 1; } else { right = mid - 1; } } return idx; } // 寻找 < target的最大索引位置 private int searchLastLess(int[] sorted, int target) { int left = 0, right = sorted.length - 1; // 默认值-1表示没找到 int idx = -1; while (left <= right) { int mid = (left + right) / 2; if (sorted[mid] < target) { // 每次找到一个合格的值就记录它，但不立刻返回 // 不断二分缩小区间 idx = mid; // left继续向右找，看有没有更大的合格的值 left = mid + 1; } else { right = mid - 1; } } return idx; } // 把start及后面的位全部置为sorted数组中的最后一个元素值（最大值） private void fillMaxFrom(int start, char[] result, int[] sorted) { int maxDigit = sorted[sorted.length - 1]; for (int i = start; i < result.length; i++) { result[i] = (char) (maxDigit + '0'); } } // 构建长度为len的全部由sorted数组的最后一位组成的数组（此处的len即为n的长度len - 1） private String buildAllMax(int len, int[] sorted) { if (len <= 0) return ""; int maxDigit = sorted[sorted.length - 1]; char[] res = new char[len]; Arrays.fill(res, (char) (maxDigit + '0')); return new String(res); } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String n = scanner.nextLine().trim(); int m = scanner.nextInt(); int[] digits = new int[m]; for (int i = 0; i < m; i++) { digits[i] = scanner.nextInt(); } Solution solution = new Solution(); String result = solution.maxLessThanN(n, digits); System.out.println(result); scanner.close(); } }