LeetCode 补充题 151. 字符串中最大的三个不同整数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 215. 数组中的第 K 个最大元素
LeetCode 原题从整数数组中选出第 k 大元素，重复值参与排名；本文先解析字符串中的整数、按数值去重，再返回最大的三个值。
:::
给定字符串
s，按[+-]?[0-9]+识别其中的整数片段，允许正负号和前导零。按数值去重后，返回最大的三个整数的规范十进制字符串，按数值降序排列；不足三个时返回全部。
示例 1：
输入：
s = "a001b2c100d2e0009"
输出：["100","9","2"]
解释： 规范化后不同值为 1、2、100、9，取最大的三个。
示例 2：
输入：
s = "-12 x000 y12"
输出：["12","0","-12"]
解释： 正数 12、0 和负数 -12 是三个不同值，按数值降序返回。
提示：
- 正负号只有紧邻数字时才属于该数。
- 数字长度可以超过
64位范围。 -
-0、+0、000视为同一数值0。
题意分析
需要先识别完整整数片段，再按数值而非文本去重。数字可能超过 64 位，前导零和正负零又可能产生不同写法，因此用大整数统一解析后再比较。
解法：解析大整数并维护三个候选
核心思路
[!blue]
按
[+-]?[0-9]+从左到右读取不重叠片段，符号只有紧邻数字时才被匹配。转换为大整数后，+001与1相等，各种零写法也都归一为 0。始终只保存当前见过的最大三个不同数值。新值与候选重复就跳过，否则插入并在超过三个时删除最小值；Java 用有序集合，Go 对至多四个候选排序。
第三大门槛只会不变或升高，所以之前被淘汰的较小数以后再次出现也不可能改善答案，无需另存全部历史值。最后按数值降序转回规范十进制字符串；没有数字片段时返回空列表。
解题步骤
- 解析完整整数片段，用大整数归一化符号和前导零。
- 将新值加入至多三个候选中；重复值跳过。
- 按数值保留最大三个，最终转回十进制字符串。
代码实现
class Solution {
public List<String> topThreeIntegers(String s) {
TreeSet<BigInteger> best = new TreeSet<>();
Matcher matcher = Pattern.compile("[+-]?[0-9]+").matcher(s);
while (matcher.find()) {
best.add(new BigInteger(matcher.group()));
if (best.size() > 3) {
best.pollFirst();
}
}
List<String> out = new ArrayList<>();
for (BigInteger value : best.descendingSet()) {
out.add(value.toString());
}
return out;
}
}
import (
"math/big"
"regexp"
"sort"
)
func topThreeIntegers(s string) []string {
pattern := regexp.MustCompile(`[+-]?[0-9]+`)
best := []*big.Int{}
for offset := 0; offset < len(s); {
match := pattern.FindStringIndex(s[offset:])
if match == nil {
break
}
value, _ := new(big.Int).SetString(s[offset+match[0]:offset+match[1]], 10)
offset += match[1]
exists := false
for _, x := range best {
if x.Cmp(value) == 0 {
exists = true
break
}
}
if exists {
continue
}
best = append(best, value)
sort.Slice(best, func(i, j int) bool {
return best[i].Cmp(best[j]) > 0
})
if len(best) > 3 {
best = best[:3]
}
}
out := make([]string, len(best))
for i, value := range best {
out[i] = value.String()
}
return out
}
复杂度分析
- 时间复杂度：扫描字符 $O(C)$，另计大整数解析和比较成本。
- 空间复杂度：最多保留四个候选，额外空间由最长数字片段的位数决定。
关键点总结
[!green]
第三大门槛只会上升；被淘汰的小值以后即使再次出现，也不会重新超过门槛，因此不必保存全部历史数字。
易错点总结
[!yellow]
按数值而不是字符串字典序比较；不同前导零写法与正负零必须归为同一个值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 414. 第三大的数 | 简单 | 都是维护三个不同最大值，本题额外从文本解析任意精度整数并返回全部三个候选。 |
| 215. 数组中的第K个最大元素 | 中等 | 原题按元素重数求第 k 大，本题先按数值去重且 k 固定为 3。 |