0414. Third Maximum Number¶
题目信息¶
- 题号:
0414
- 难度:
Easy
- 主题:
不同数值、第三大、重复元素、最大值回退
- 原题:
- 重点:
排名按不同数值计算、重复值只占一个名次、不同值不足三个时返回最大值
题目重述¶
给定整数数组 nums,返回数组中第三大的不同数值。重复出现的相同整数只算一个名次;若数组中不同数值少于三个,则返回其中的最大值。
nums.length 位于 [1, 10^4],每个元素都在 32 位有符号整数范围内。-2^31 等边界值与其他整数一样是合法候选,不能把某个整数值用作“尚未设置”的特殊标记。
自建示例¶
重复最大值不重复占名次:
输入:nums = [9, 2, 9, 7, 5]
输出:5
解释:不同数值按降序为 9、7、5、2,因此第三大不同值是 5。
不同值不足三个:
输入:nums = [4, 4]
输出:4
解释:数组只有一个不同数值,按题目要求返回最大值 4。
只保留最大的三个不同值¶
用有序集合维护当前见过的最大三个不同数值。插入重复值不会改变集合;插入新值后若集合超过三个,就删除最小值。扫描结束时,集合大小为 3 则最小者是第三大,否则最大者是题目要求的回退答案。
C++ 实现¶
class Solution {
public:
int thirdMax(std::vector<int>& nums) {
std::set<int> top;
for (int value : nums) {
top.insert(value);
if (top.size() > 3) top.erase(top.begin());
}
if (top.size() == 3) return *top.begin();
return *top.rbegin();
}
};
代码分析¶
集合既去除重复名次,又把维护规模限制为 3,不需要使用可能与合法输入冲突的哨兵值;-2^31 也能正常存储。每次操作是固定大小集合上的 O(log 3),总体时间可视为 O(n),额外空间为 O(1)。