知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 小于 n 的最大数字 ## 题目 给定一个字符串 `n`(表示一个正整数)和一个整数数组 `digits`(包含 1~9 的数字,可重复使用), 找出用 `digits` 中的数字能组成的 **小于 n 的最大整数**。 ``` 输入:n = "23121", digits = [1,2,3,4] 输出:"23114" 输入:n = "1234", digits = [1,2,3] 输出:"1233" 输入:n = "1000", digits = [1,2,3] 输出:"333" ← 位数可以比 n 少 输入:n = "99", digits = [9] 输出:"9" ``` ## 核心思路 ``` 从高位到低位尝试与 n 保持相同前缀。 当某个位置无法匹配时(该位数字不在 digits 中), 向左回退,找到第一个可以"减小"的位置: → 放一个比 n[i] 小的最大可用数字 → 剩余位置全部填最大可用数字 如果所有位置都无法减小 → 返回位数少一位、全填最大数字。 ``` ### 图解过程 ``` n = "23121", digits = [1,2,3,4](可用数字 1,2,3,4,4 最大) 遍历: i=0: n[0]=2, 2 在 digits 中 ✓ → 暂存 2 i=1: n[1]=3, 3 在 digits 中 ✓ → 暂存 3 i=2: n[2]=1, 1 在 digits 中 ✓ → 暂存 1 i=3: n[3]=2, 2 在 digits 中 ✓ → 暂存 2 i=4: n[4]=1, 1 在 digits 中 ✓ → 但需要 < n,最后一位不能同样的 回退到 i=3:找比 2 小的最大数字 → 1 存在! 结果前缀 = "231" + "1" = "2311" 剩余 1 位填最大数字 4 → "23114" 验证:23114 < 23121 ✓ ``` ## 解法一:贪心(推荐,O(n)) ```java public class Solution { public String maxNumberLessThanN(String n, int[] digits) { // 1. 预处理:digits 排序 + 去重 TreeSet<Integer> set = new TreeSet<>(); for (int d : digits) set.add(d); int maxDigit = set.last(); // 最大可用数字 char[] s = n.toCharArray(); int[] result = new int[s.length]; // 2. 从左到右尝试匹配,记录每个位置的选择 for (int i = 0; i < s.length; i++) { int cur = s[i] - '0'; // 2a. 当前位存在于 digits 中 → 先用它,继续往后看 if (set.contains(cur)) { result[i] = cur; continue; } // 2b. 当前位不在 digits 中 → 尝试在当前位放更小的数字 Integer smaller = set.lower(cur); if (smaller != null) { result[i] = smaller; fillRemaining(result, i + 1, maxDigit); return buildString(result); } // 2c. 当前位没有更小数字 → 向左回退 int j = i - 1; while (j >= 0) { Integer backSmaller = set.lower(result[j]); if (backSmaller != null) { result[j] = backSmaller; fillRemaining(result, j + 1, maxDigit); return buildString(result); } j--; } // 2d. 所有位都无法减小 → 返回位数少一位的全最大数字 return buildAllMax(s.length - 1, maxDigit); } // 3. 前缀完全匹配 n → n 本身就是由 digits 构成,需要找到 < n 的 // 从末位向左找第一个可以减小的位置 for (int i = s.length - 1; i >= 0; i--) { Integer smaller = set.lower(result[i]); if (smaller != null) { result[i] = smaller; fillRemaining(result, i + 1, maxDigit); return buildString(result); } } // 所有位都减不了 → 返回少一位的 return buildAllMax(s.length - 1, maxDigit); } // 从 index 开始,剩余位置填 maxDigit private void fillRemaining(int[] result, int start, int maxDigit) { for (int i = start; i < result.length; i++) { result[i] = maxDigit; } } // 构成长度为 len、每位都是 maxDigit 的字符串 private String buildAllMax(int len, int maxDigit) { if (len == 0) return "0"; StringBuilder sb = new StringBuilder(); for (int i = 0; i < len; i++) sb.append(maxDigit); return sb.toString(); } private String buildString(int[] arr) { StringBuilder sb = new StringBuilder(); for (int num : arr) sb.append(num); return sb.toString(); } } ``` ## 解法二:DFS + 剪枝(更直观) ```java class Solution { private TreeSet<Integer> set; private int maxDigit; private String n; private String ans = ""; public String maxNumberLessThanN(String n, int[] digits) { set = new TreeSet<>(); for (int d : digits) set.add(d); maxDigit = set.last(); this.n = n; dfs(0, true, new StringBuilder()); return ans.isEmpty() ? buildAllMax(n.length() - 1) : ans; } /** * @param pos 当前处理的位 * @param tight 是否受 n 的约束(前面都相等) * @param path 当前构造的数字 */ private void dfs(int pos, boolean tight, StringBuilder path) { // 剪枝:当前已经比已知答案小,不用继续 if (!ans.isEmpty() && path.length() <= ans.length()) { String cur = path.toString(); String prefix = ans.substring(0, Math.min(cur.length(), ans.length())); if (cur.compareTo(prefix) < 0) return; } if (pos == n.length()) { String candidate = path.toString(); if (candidate.compareTo(n) < 0) { ans = candidate; } return; } int limit = tight ? n.charAt(pos) - '0' : 9; // 从大到小尝试当前位的数字(贪心:先试大的) Integer digit = set.floor(limit); while (digit != null) { path.append(digit); dfs(pos + 1, tight && digit == limit, path); path.deleteCharAt(path.length() - 1); if (!ans.isEmpty()) return; // 找到答案立即剪枝 digit = set.lower(digit); } // 当前位不填(允许结果位数少于 n)— 只有 pos > 0 时允许 // 相当于从这一位开始全部不填,后续填最大数字 if (pos > 0 && ans.isEmpty()) { String prefix = path.toString(); StringBuilder candidate = new StringBuilder(prefix); for (int i = pos; i < n.length(); i++) { candidate.append(maxDigit); } String cand = candidate.toString(); if (cand.compareTo(n) < 0) { ans = cand; } } } private String buildAllMax(int len) { if (len <= 0) return "0"; StringBuilder sb = new StringBuilder(); for (int i = 0; i < len; i++) sb.append(maxDigit); return sb.toString(); } } ``` ## 解法三:极简贪心(一次遍历,推荐面试手写) ```java public String maxNumberLessThanN(String n, int[] digits) { TreeSet<Integer> set = new TreeSet<>(); for (int d : digits) set.add(d); int max = set.last(); char[] s = n.toCharArray(); int len = s.length; // 第一遍:尝试每位放 ≤ n[i] 的最大数字 int[] res = new int[len]; for (int i = 0; i < len; i++) { int cur = s[i] - '0'; Integer best = set.floor(cur); if (best == null) { // 当前位放不了任何数字 → 回退 int j = i - 1; while (j >= 0) { Integer smaller = set.lower(res[j]); if (smaller != null) { res[j] = smaller; for (int k = j + 1; k < len; k++) res[k] = max; return arrToStr(res); } j--; } // 回退到最左 → 位数少一位 return lenMinusOne(max, len - 1); } res[i] = best; if (best < cur) { // 当前位已小于 n[i],后面全填最大 for (int k = i + 1; k < len; k++) res[k] = max; return arrToStr(res); } } // 完全匹配 n → 需要缩小 for (int i = len - 1; i >= 0; i--) { Integer smaller = set.lower(res[i]); if (smaller != null) { res[i] = smaller; for (int k = i + 1; k < len; k++) res[k] = max; return arrToStr(res); } } return lenMinusOne(max, len - 1); } private String arrToStr(int[] arr) { StringBuilder sb = new StringBuilder(); for (int x : arr) sb.append(x); return sb.toString(); } private String lenMinusOne(int maxDigit, int len) { if (len <= 0) return "0"; StringBuilder sb = new StringBuilder(); for (int i = 0; i < len; i++) sb.append(maxDigit); return sb.toString(); } ``` ## 复杂度 | 解法 | 时间 | 空间 | |------|:---:|:---:| | 贪心(一次遍历) | O(n) | O(n) | | DFS + 剪枝 | O(n) | O(n) | n 为数字字符串长度,digits 最多 9 个。 ## 边界情况 | n | digits | 输出 | 说明 | |----|--------|------|------| | "1000" | [1,2,3] | "333" | 位数可减少 | | "1" | [2,3] | "0" | 没有更小的,降位归零 | | "99" | [9] | "9" | 回退到一位 | | "5" | [1,2,3,4,5] | "4" | 完全匹配需缩小 | | "23121" | [2] | "22222" | 只能用一种数字 | ## 一句话总结 从左到右尽量匹配 n 的前缀,遇到无法匹配的位置就向左回退找第一个"可减小"的位置,放更小数字后全部填最大数字。O(n) 一遍遍历即可。 --- ## 延伸:如果 digits 包含 0 且要求数字不能有前导零 ```java // 额外处理:第一位不能放 0(除非结果就是 "0") if (i == 0 && set.floor(cur) == 0 && set.size() == 1) { return "0"; // digits 只有 {0},结果只能是 0 } ``` --- ## 同类题目 | 题目 | 描述 | |------|------| | [46 - 下一个排列](file:///f:/KiroPro/Text/java/46-next-permutation.md) | 找比当前数字大的最小排列 | | 最大交换(LeetCode 670) | 最多交换两个数字使结果最大 | --- 上一篇:[83 - 前 K 个高频元素](file:///f:/KiroPro/Text/java/83-top-k-frequent.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入