LeetCode 补充题 162. 指定数字组成的小于 N 的最大整数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 902. 最大为 N 的数字组合
:::
给定非空数字集合
digits和无前导零的正整数字符串N。digits中的元素属于1…9，每个数字可以无限复用。构造严格小于
N的最大正整数，以字符串返回；不存在时返回空字符串。
示例 1：
输入：
digits = [1,3,5], N = "321"
输出："315"
解释： 315 的每一位均可选，且它是严格小于 321 的最大可构造整数。
示例 2：
输入：
digits = [1,3,5], N = "111"
输出："55"
解释： 111 本身不符合严格小于要求，无法构造更小的三位数，因此选择最大的两位数 55。
示例 3：
输入：
digits = [5], N = "5"
输出：""
解释： 无法构造严格小于 5 的正整数，返回空字符串。
提示：
-
digits为非空集合，元素属于1…9，每个数字可无限使用。 -
N是无前导零的正整数字符串。 - 结果必须严格小于
N，不存在时返回空字符串。
题意分析
无前导零的正整数先按位数比较，同位数再按字典序比较。因此优先找与
N等长的答案，并让相同前缀尽量长；只有等长答案不存在时，才降为少一位。
解法：保持相同前缀，回退降位后填满后缀
核心思路
[!blue]
从左到右，只要
N当前数字可选，就保留相同前缀。在第一个无法相等的位置，尝试最大的可用且更小的数字；一旦选到，整个数已严格小于N，后缀便可全部填集合最大值。若当前位无法降低，就向前回退到最近可以降低的位置。越靠右才降低，保留的高位相同前缀越长，数值越大；同一位置又选择最大的较小数字，所以得到最优的等长结果。
N每一位都可选时也必须从末位回退，排除与N相等的情况。所有位置都无法降低时不存在等长解。数字可无限复用且不含 0，少一位并全部取最大数字就是所有更短正整数中的最大值；原长度为 1 时此结果为空串，表示无解。
解题步骤
- 建立可用数字表与最大可用数字，尽量沿 N 的相同前缀前进。
- 在首个无法相等的位置找最大且更小的可用数字；找不到就向前回退。
- 一旦成功降低某位，用最大可用数字填满后缀。
- 若等长方案不存在，返回少一位的全最大数字；长度变为 0 时即无解。
代码实现
class Solution {
public String largestBelow(int[] digits, String n) {
boolean[] allowed = new boolean[10];
int maximum = 0;
for (int d : digits) {
allowed[d] = true;
maximum = Math.max(maximum, d);
}
char[] out = n.toCharArray();
int i = 0;
while (i < out.length && allowed[out[i] - '0']) {
i++;
}
if (i == out.length) {
i--;
}
for (; i >= 0; i--) {
for (int d = n.charAt(i) - '0' - 1; d >= 1; d--) {
if (allowed[d]) {
out[i] = (char) ('0' + d);
Arrays.fill(out, i + 1, out.length, (char) ('0' + maximum));
return new String(out);
}
}
}
return String.valueOf((char) ('0' + maximum)).repeat(n.length() - 1);
}
}
import "strings"
func largestBelow(digits []int, n string) string {
allowed := [10]bool{}
maximum := 0
for _, d := range digits {
allowed[d] = true
maximum = max(maximum, d)
}
out := []byte(n)
i := 0
for i < len(out) && allowed[out[i]-'0'] {
i++
}
if i == len(out) {
i--
}
for ; i >= 0; i-- {
for d := int(n[i]-'0') - 1; d >= 1; d-- {
if allowed[d] {
out[i] = byte('0' + d)
for j := i + 1; j < len(out); j++ {
out[j] = byte('0' + maximum)
}
return string(out)
}
}
}
return strings.Repeat(string(byte('0'+maximum)), len(n)-1)
}
复杂度分析
- 时间复杂度：$O(\lvert N\rvert+\lvert digits\rvert)$。
- 空间复杂度：结果空间 $O(\lvert N\rvert)$，数字表空间 $O(1)$。
关键点总结
[!green]
等长正整数按字典序比较；越晚降低某一位越好，降低后所有后缀都应尽可能大。
易错点总结
[!yellow]
原题统计不大于N的数量，本题构造严格小于N的数；完整匹配N时不能直接返回。数字0不在本题集合中。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 902. 最大为 N 的数字组合 | 困难 | 原题计数不大于 N 的数字，本题构造严格小于 N 的最大值，完整相等时必须回退。 |
| 738. 单调递增的数字 | 中等 | 都在某位减小后尽量填大后缀；原题限制数位单调，本题限制可使用的数字集合。 |