企业官网建设流程全解析

• 文档
• 教程
• 知识库

本篇题解来自 InterviewGuide 仓库中「精选力扣 300+ 题目之数组」题单（题单目录）。LeetCode 414「第三大的数」是一道非常适合面试热身与手撕的高频 Easy 题：题目明确要求时间复杂度为 O(n)，意味着不能直接排序后取下标，必须用一趟遍历配合三个变量完成前三大的实时维护，同时还要处理"重复元素只算一次"与"不存在第三大数时返回最大数"这两个隐藏的坑。读完本文，你将掌握这一套可复用的"Top-3 扫描"模板，并理解其为何能推广到更一般的 Top K 场景。

一、题目回顾：从原题出发

原文档给出的题目描述如下：

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是 O(n)。

注意题目有两个隐含约束，它们是本题区别于"简单排序取数"的关键：

1. 第三大且唯一出现的数：重复元素按一个算，例如[2, 2, 3, 1]中，去重后的集合是{1, 2, 3}，第三大的数是 1，而不是 2；
2. 时间复杂度必须是 O(n)：排序需要 O(n log n)，不符合题目要求，必须另辟蹊径。

示例一：普通情况

输入: [3, 2, 1] 输出: 1 解释: 第三大的数是 1.

数组恰好有三个不同的元素，第三大的数就是最小的那个 1。

示例二：不足三个不同元素

输入: [1, 2] 输出: 2 解释: 第三大的数不存在, 所以返回最大的数 2 .

数组中只有两个不同的数，不存在第三大的数，因此按题目要求返回最大数 2。

示例三：重复元素只算一次

输入: [2, 2, 3, 1] 输出: 1 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 存在两个值为2的数，它们都排第二。

2出现了两次，但它们只占据"第二大"这一个名次，去重后的前三名依次是 3、2、1，所以第三大的数是 1。这个示例直接点破了本题最容易写错的地方——必须用严格的大小比较来跳过重复值。

二、为什么不能排序？——题目约束与思路推导

如果把数组sort之后再取倒数第三个元素，思路虽然直观，但std::sort的时间复杂度是 O(n log n)，违背了题目"必须是 O(n)"的硬性要求。

因此正确的方向是单次线性扫描 + 常数个变量：

• 遍历过程中实时维护"当前遇到的最大值、第二大值、第三大值"三个候选；
• 每读到一个新元素，就尝试把它插入前三名的正确位置；
• 扫描结束时，三个变量里就存放着整个数组的前三名（去重意义上）。

这与 InterviewGuide 仓库中关于Top K 问题的论述一脉相承。在 高频算法考点整理 中记录了解决 Top K 问题的若干方法，其中"使用选择排序的思想，对前 K 个元素部分排序——扫描一遍数组，选出最大的一个元素，然后再扫描一遍数组，找出第二大的元素，再扫描一遍数组，找出第三大的元素……以此类推，找 K 个元素，时间复杂度为 O(N×K)"。本题正是该思想的特例：K 固定为 3，于是可以把"多趟扫描"合并进一趟扫描 + 三个变量，把 O(N×K) 优化为 O(N)。而堆与 Quick Select 是更大 K 值下的通用解法，本题用三个变量即可，连堆都省了。

三、第一版解法（有参考）：三变量哨兵法

仓库原文档给出了如下参考实现，并记录了当时的提交数据：执行用时 4 ms（击败 99.23% 的 C++ 提交）、内存消耗 9.1 MB（击败 67.43% 的提交）。

int thirdMax(vector<int>& nums) { long long firstNum = LONG_MIN, secondNum = LONG_MIN, thirdNum = LONG_MIN; for (auto& a : nums) { if (firstNum < a) { thirdNum = secondNum; secondNum = firstNum; firstNum = a; } else if (firstNum > a && secondNum < a) { thirdNum = secondNum; secondNum = a; } if (secondNum > a && thirdNum < a) { thirdNum = a; } } if (thirdNum == LONG_MIN) return firstNum; else return thirdNum; }

下面逐段拆解这个解法的设计精髓。

3.1 为什么三个变量要用long long且初始化为LONG_MIN

这是整份代码最容易被忽略、却最关键的技巧。

如果直接定义int first, second, third，那么初值该填多少？常见错误是填INT_MIN或INT_MIN - 1（未定义行为）。而数组元素本身就是int，取值范围可以覆盖到INT_MIN。设想数组为[-1, -2, -3]：

• 若用INT_MIN做哨兵，扫描到-1时，firstNum变为-1；扫描到-2时，secondNum变为-2；扫描到-3时，thirdNum变为-3；
• 但如果数组里有元素恰好等于INT_MIN，哨兵值就会被"误判"成一个真实存在的第三大数，导致结果错误。

改用long long并把初值设为LONG_MIN（在 64 位平台上约等于 -9.2×10¹⁸），该值严格小于任何可能的int元素，因此可以放心地作为"尚未填入"的哨兵使用。这正是本题在 C++ 下的经典写法：用更宽的整数类型 + 极值哨兵，规避元素范围覆盖哨兵值的问题。

3.2 三个分支的语义：严格比较保证"去重"

代码用三个连续的判断（而非if/else if/else串行）完成前三大名的维护，每个分支都使用了严格不等号，这是满足示例三"唯一出现的数"约束的根本保障：

• 分支一firstNum < a：当前元素打破了最大纪录。此时原来的第一名降为第二名、原来的第二名降为第三名，a荣登第一名。
• 分支二firstNum > a && secondNum < a：当前元素介于第一名与第二名之间。它成为新的第二名，原来的第二名降为第三名。
• 分支三secondNum > a && thirdNum < a：当前元素介于第二名与第三名之间，直接刷新第三名。

三个分支各自使用>与<的严格比较，意味着等于某个名次的重复元素不会被任何分支接纳。以[2, 2, 3, 1]为例：

1. 读入2：firstNum = 2；
2. 读入第二个2：firstNum < 2不成立（相等），firstNum > 2 && secondNum < 2不成立，secondNum > 2 && thirdNum < 2不成立，被整体跳过——重复的 2 没有产生新名次；
3. 读入3：firstNum(2) < 3成立，第三名 = 第二名 =LONG_MIN，第二名 = 2，第一名 = 3；
4. 读入1：前两个分支不成立，secondNum(2) > 1 && thirdNum(LONG_MIN) < 1成立，thirdNum = 1。

最终thirdNum = 1，与题目预期完全一致。注意这里第三个判断没有else if前缀，它独立于前两个分支执行——但当分支一或分支二触发时，a必然大于旧的第二名/第三名，因此第三个条件secondNum > a天然不成立，不会产生错误更新，代码在逻辑上是自洽的。

3.3 收尾判断：第三大数是否存在

遍历结束后：

if (thirdNum == LONG_MIN) return firstNum; else return thirdNum;

thirdNum是否仍停留在哨兵值LONG_MIN，等价于"整个数组（去重后）是否凑不够三个不同的数"。若凑不够，按题目要求返回最大数firstNum；否则返回thirdNum。这精确覆盖了示例二[1, 2]这类边界场景。

四、算法复杂度与边界情况验证

边界情况逐一验证：

• 数组只有一个元素：只有firstNum被更新，thirdNum保持LONG_MIN，返回firstNum（即该元素本身），符合"不存在第三大则返回最大数"；
• 数组只有两个不同元素（如[1, 2]）：thirdNum保持哨兵值，返回最大数 2，与示例二一致；
• 元素全为负数：由于哨兵是LONG_MIN而非 0，负数可以正常参与前三大名次的角逐，结果正确；
• 元素恰好等于INT_MIN：LONG_MIN哨兵依然严格小于它，不会被误判，这是选择long long而非int的根本原因；
• 大量重复元素（如[5,5,5,5]）：去重后只有一个不同值，thirdNum保持哨兵值，返回 5，语义正确。

五、从本题到 Top K：解法的横向扩展

本题本质上是"求第 K 大的数"在 K=3 时的特例。InterviewGuide 仓库在 高频算法考点整理 中系统整理了 Top K 问题的常见解法，可作为本题的延伸阅读：

1. 堆（priority_queue）：维护一个大小为 K 的最小堆，新元素大于堆顶则替换并调整堆，堆顶即第 K 大的元素。堆的插入为 O(log K)，整体 O(n log K)。本题 K=3，堆的常数开销反而比三个变量大，故直接用变量更优；
2. Quick Select：脱胎于快速排序，每次按枢轴划分后只递归处理包含第 K 大的一侧，平均 O(n)；
3. 排序后取下标：O(n log n)，不满足本题约束；
4. 多趟扫描 / 选择排序思想：每趟找第 i 大，共 K 趟，O(n×K)。本题的"一趟扫描 + 三变量"正是该方法在 K=3 时的最优落地形态。

面试时可以这样回答面试官：K 很小（如 3 或 5）时用常数个变量线性扫描；K 较大时改用最小堆或 Quick Select。本题考察点正在于能否识破"不能排序"的约束，并用哨兵技巧优雅地处理INT_MIN级别的边界数据。

六、仓库上下文：本题在 InterviewGuide 题单中的位置

本题收录于 InterviewGuide 的 LeetCode 数组题单 Easy 分类，同题解还汇总在 数组 Easy 题解总览 中，与 581「最短无序连续子数组」、605「种花问题」、628「三个数的最大乘积」、643「子数组最大平均数 I」等题目共同构成数组类 Easy 刷题序列。其中 628. 三个数的最大乘积 同样涉及"Top-3 元素"的维护，与本解法的三变量思路互为印证，建议对比练习：628 关注的是"前三大与最小两数"的组合乘积，而 414 关注的是去重后的第三大值，二者放在一起能更好地掌握"维护极值集合"这一类题的套路。

// 完整可运行的提交版本（包含必要的头文件） #include <vector> #include <climits> using namespace std; class Solution { public: int thirdMax(vector<int>& nums) { long long firstNum = LONG_MIN, secondNum = LONG_MIN, thirdNum = LONG_MIN; for (auto& a : nums) { if (firstNum < a) { thirdNum = secondNum; secondNum = firstNum; firstNum = a; } else if (firstNum > a && secondNum < a) { thirdNum = secondNum; secondNum = a; } if (secondNum > a && thirdNum < a) { thirdNum = a; } } if (thirdNum == LONG_MIN) return firstNum; else return thirdNum; } };

将上述代码提交至力扣即可验证：示例一返回 1，示例二返回 2，示例三返回 1，全部通过。核心心法只有一句话：一趟扫描、三个变量、严格比较、极值哨兵——记住这十六个字，面试遇到"第 K 大 / 前三名"类题目时就能举一反三。

• 文档
• 教程
• 知识库