企业官网建设流程全解析

今天聊一道非常适合拿来当每日一题的经典题：LeetCode 414，第三大的数。别看题目名字直白，它其实在“第几大”这个主题里埋了不少细节，尤其是题干里那个很容易被忽略的限定词“不同”。我最初做这题时，第一版代码不到十行，一提交却错了，原因就是没把重复数字处理好。这篇笔记会完整拆解题目规则、三种解法的取舍、最优解的原理，以及我实际写码时踩过的坑，希望对正在刷题或者准备面试的你有点帮助。

这道题基本上属于“会者不难，难者忽略条件”的典型。它在面试中出现的频率不算低，因为代码量小、边界情况多，非常适合考察候选人读题是否仔细、对复杂度有没有概念、能不能把一个看似简单的问题讲完整。你一旦掌握这题，再往“第K大”“数据流中的第K大”延伸，会发现思路是贯通的。

1. 题目本身不复杂，但三个细节决定生死

1.1 原题到底在问什么

题目原文可以概括成一句话：给定一个非空整数数组，返回数组中第三大的不同数字；如果第三个最大的不同数字不存在，则返回数组中最大的数字。

我当初读题时，注意力全在“第三大”这三个字上，忽略了“不同”。后来复盘才意识到，这道题的正确性完全取决于你对三件事的理解是否到位。

第一，数组是非空的。这看起来像废话，但它意味着你不需要额外写空数组的防御逻辑。不过数组长度可能是1，也可能是2，这两种情况都必须正确处理。

第二，“第三大”指的是第三大的不同值。也就是说，重复出现的数字只能算一个候选值。比如数组<span> [1, 2, 2, 3]，不同数字只有1、2、3三个，第三大是1。如果你不管“不同”直接按大小取倒数第三个，会得到2，这就是错的。

第三，返回值是数值本身，不是下标，也不是出现次数。面试时有人会把这道题和“找第三个最大元素的下标”混淆，问出来的时候就知道题没读明白。

1.2 “不同”两个字为什么能改变结果

为了把这一点讲透，我们来看两组对比。

第一组是<span> [1, 2, 2, 3]。如果完全忽略“不同”，把数组排序得到[1, 2, 2, 3]，倒数第三个元素是2。但是把重复值去掉之后，不同数字只有3、2、1，第三大的不同值是1。同一个数组，两种理解，结果差了整整一档。

第二组是 LeetCode 官方示例里的<span> [2, 2, 3, 1]。忽略“不同”的排序法和正确解法不一样，但答案稍微巧一点，这里我不展开具体数值，你只要记住不同数字是3、2、1，第三大是1就够。真正有意思的是下面这种：

[1, 1, 2]

如果无视“不同”，排序后是[1, 1, 2]，倒数第三个是1。但去掉重复值之后，不同数字只有2、1两个，数量不足三个，所以按题目规则应该返回最大值2。

也就是说，“不同”这个词不仅影响“第三大是谁”，还会影响“第三大到底存不存在”。这种要命的细节，必须在一开始就咬住。

1.3 返回值规则的另一种理解

我习惯把这道题的规则翻译成一句白话：把所有不同的数字从大到小排成一列，如果这一列至少有三个，就返回第三个；如果不够三个，就返回第一个。

更形式化一点，设s是数组所有不同数字组成的集合。如果|s| >= 3，答案就是把s按降序排列后的第三个数；如果|s| < 3，答案就是max(s)。

注意“不足三个就返回最大值”这一点，很多人会理解成“返回第三大的不存在时按最大值兜底”，这么说没错，但实际代码里你要做的是判断第三大的位置有没有被填上，而不是先排序再判断。这个区别在后面的三个变量解法里会体现得很明显。

还有一个容易搞混的地方：如果数组是[-1, -2, -3]，第三大的不同值是-3，不是-1。负数参与排序时，很多人会被“最大值”“最小”绕晕，实际上只要把所有数字按从大到小排，位置关系完全一样。

2. 三种解法：从最笨到最优，各自适合什么场景

2.1 集合去重加排序：五行的保守解法

如果你只是想快速通过用例，最直白的写法是这样：

def thirdMax(nums): uniq = sorted(set(nums)) if len(uniq) < 3: return uniq[-1] return uniq[-3]

set(nums)负责去重，sorted得到升序列表。uniq[-1]是最大值，uniq[-3]是第三大的不同值。如果去重后不足三个，就返回最后一位。

这段代码的正确性很容易验证，代价是时间复杂度O(n log n)，空间复杂度O(n)。排序和集合都额外占内存，对于这个题目来说属于“能过，但不够漂亮”的方案。

不过我不建议你直接跳过它。面试的时候，这种解法有一个特殊作用：它可以作为你思考路径的起点。你先说出“最朴素的做法是先去掉重复，再排序取倒数第三个”，然后分析它的复杂度，再引出更优解法。这样面试官能看见你的思考过程，而不是看到一个凭空冒出来的奇技淫巧。

2.2 小顶堆加集合：更接近“流式处理”的思路

第二种解法是维护一个容量为 3 的小顶堆，堆里始终保存当前已经遇到过的最大三个不同数字。小顶堆的堆顶是这三者中最小的一个，也就是当前候选的第三大。

每来一个数字x，先看它是否已经出现过。如果出现过，跳过；如果没出现过，就把它加入集合，再根据堆的情况决定是否入堆：

import heapq def thirdMax(nums): heap = [] seen = set() for x in nums: if x in seen: continue seen.add(x) if len(heap) < 3: heapq.heappush(heap, x) else: if x > heap[0]: heapq.heapreplace(heap, x) if len(heap) < 3: return max(heap) return heap[0]

为什么x > heap[0]才替换？因为堆顶是当前三个最大候选里最小的那个，也就是进入前三名的门槛。如果新数字连门槛都过不去，它不可能排进前三；如果它比门槛大，那它就有资格顶掉门槛，成为新的第三大。

这里我用了一个seen集合来做重复判断。你可能会想，既然堆里最多只有三个数字，直接在堆里查重不就行了？问题是堆不是按“是否包含某个值”设计的，查重需要遍历整个堆，虽然只有三个元素遍历起来不贵，但逻辑上不够干净，而且代码维护性差。用集合辅助查重，虽然空间复杂度从O(1)变成了O(n)，却换来了清晰的语义和扩展性。这个解法的时间复杂度是O(n log 3)，因为堆大小固定，可以近似看作O(n)。

如果你把这个解法学会，再去看“数据流中的第K大”这类题，会觉得非常顺畅，因为它们的骨架几乎一样，只是堆的大小从 3 变成了k。

2.3 三个变量单次扫描：我最推荐的面试写法

我认为这道题最优、也最符合面试直觉的写法，是只用三个变量做一次扫描。

思路是维护三个变量，分别表示当前已经看到的数字里，第一大、第二大、第三大的不同值是几。数组里每个元素进来，都按照大小关系去尝试插入这三个变量组成的有序序列；如果它跟已有变量相等，就直接跳过，因为重复值不会改变任何排名。

def thirdMax(nums): first = second = third = None for x in nums: if x == first or x == second or x == third: continue if first is None or x > first: first, second, third = x, first, second elif second is None or x > second: second, third = x, second elif third is None or x > third: third = x return first if third is None else third

这段代码看起来短，但里面有几个关键点：为什么用None而不是一个很大的负数？为什么if x == first or x == second or x == third要放在最前面？为什么赋值顺序是first, second, third = x, first, second？这些问题我放到第 4 节专门讲，这里先记住结论。

复杂度上它是O(n)时间、O(1)空间，没有任何额外数据结构。对于“第三大”这种固定规模问题，这就是最优解，也最能体现你对空间复杂度的控制能力。

2.4 三种解法放在一起怎么选

我自己做这道题时，三种写法都验证过，也都跑过完整测试。结论是：如果是为了通过题目或者面试手写，三个变量法综合性价比最高；如果你想借这道题顺便复习“第K大”和“流式处理”，那堆的解法更有价值。两者不冲突，你可以都掌握。

3. 三个变量法为什么是对的：不变量与逐步推演

3.1 不变量到底是什么

很多人刷题只背代码，不理解背后的不变量，导致面试时稍微被追问两句就露馅。三个变量法的不变量是这样一句话：每处理完数组里的前i个元素之后，first、second、third分别等于前i个元素去重后的第一大、第二大、第三大；如果某个排名暂时还不存在，对应变量就是None。

这个不变量在循环开始前是成立的，因为一个元素都没处理时，三个位置都没有候选。每次迭代结束时，我要保证它依然成立。只要你能做到这一点，扫描完整数组后，三个变量自然就持有了全局答案。

而这正好解释了为什么相等判断不能省。如果first、second、third已经各自维护着三个互不相同的值，来一个和first相等的数，它当然不会改变排名；但如果少了这步判断，它可能会被错误地插进second或third的位置，把第二、第三名污染成和第一名相同的值，不变量就被破坏了。

3.2 三种分支的情况

我们逐个看新元素x进入时会发生什么。

第一种情况：x比first大，或者first还是None。这说明x是新的最大值。原来的first降为第二名，原来的second降为第三名，原来的third被挤出去。于是写：

first, second, third = x, first, second

这里有个细节：等号右边的first、second是旧值。Python 会先把右边所有表达式求值，再执行赋值，所以不会出现“覆盖了旧值导致后面取不到”的问题。

第二种情况：x不大于first，但比second大，或者second还是None。这说明x应该排在第一名和当前第二名之间。原来的second降为第三名，原来的third被挤掉：

second, third = x, second

第三种情况：x只比third大，或者third还是None。说明它只能排在第三名：

third = x

因为三个分支是互斥的，而且每次更新后都保持了“从大到小、互不相同、前三个候选”这三个性质，所以循环结束后答案就是first或third。

为了直观一点，你可以拿[5, 1, 4, 3]自己在纸上走一遍。前两个元素让first=5, second=1；第三个元素4插在中间，让second=4, third=1；第四个元素3只比third大，所以最终third=3。不同数字降序是5、4、3，第三大确实是3。

3.3 为什么三个变量就够，不需要第四个

这是面试官最喜欢追问的问题。答案是：题目最终只要第三大的值，这个值只依赖前三大的三个不同数字。任何排在第四名及更后面的数字，都不会影响前三名的组成。

你可以反过来想，如果维护四个变量会不会改变答案？不会。第四个位置唯一可能被用到的情况，是第三名被挤出后新的第三名需要某个值填充，但新第三名要么来自原来的第二名，要么来自新来的元素，压根不需要旧第四名。所以三个变量就是刚好够用的状态，这也是O(1)空间的底气来源。

如果题目改成“返回第四大的不同数字”，那就要再多维护一个变量，或者干脆改用大小为 4 的堆。规律是：要找第k大，就需要维护前k大。固定k时用变量，不固定时用堆。

4. 写代码时最容易掉进去的坑，以及我怎么避开的

4.1 哨兵值：为什么我不用负无穷，用 None

网上很多版本的三个变量解法会用float('-inf')作为初始值，然后循环结束后检查third是否还是负无穷，来判断第三大是否存在：

# 这种写法有隐患 def thirdMax(nums): first = second = third = float('-inf') for x in nums: if x > first: first, second, third = x, first, second elif x > second: second, third = x, second elif x > third: third = x return first if third == float('-inf') else third

这段代码跑 LeetCode 原题大概率能过，因为测试数据是整数数组，不会出现负无穷。但它把“第三大不存在”和“第三大恰好等于一个特定值”这两种情况混在一起了。假设某个业务系统允许输入float('-inf')，那当数组是[1, 2, float('-inf')]时，正确答案应该返回float('-inf')，但上面的代码会以为第三大不存在，错误地返回1。

我更推荐用None表示“还没填上”，因为None不会和任何整数相等，判断逻辑从“值比较”变成了“状态判断”，语义更清晰。

4.2 重复判断必须放在最前面

重复判断不是为了优化速度，而是为了维持变量之间的互异性。来看一个反例。

数组[3, 3, 2, 1]，正确答案是多少？不同数字是3、2、1，第三大是1。

如果没有最前面的continue去重，代码会怎么执行？第一个3让first=3；第二个3进来时，因为x > first不成立，而second is None成立，它会被塞进second，于是first=3, second=3。接着2填进third，最后返回2。这就是错误答案。

真正正确的结果应该是1，因为第二个3是重复值，它不应该占据第二名的位置。所以if x == first or x == second or x == third: continue不是可选优化，是必要逻辑。

4.3 变量更新顺序写反是高频错误

如果不用 Python 的元组赋值，很容易写错成：

# 错误示例 first = x second = first third = second

第一次更新没问题，但第二次更新时，second拿到的已经是新的first，而不是旧的first。这样会导致两个变量存同一个值，整个算法就废了。

正确的等价写法是先用临时变量保存旧值：

old_first, old_second = first, second first = x second = old_first third = old_second

这种写法更直白，适合不习惯元组赋值的人。其实很多看起来“巧妙”的代码，本质上就是做了这么一件事：先取旧值，再按优先级往下移动。想清楚这一点，你怎么写都不会错。

5. 从“第三大”到“第K大”，以及流式场景的延伸

5.1 改成第K大之后的写法

三个变量法只适用于k=3。如果题目改成“返回第k大的不同数字”，最佳方案是堆。因为k可能是任意值，你不可能写几百个变量。

import heapq def kth_largest_distinct(nums, k): heap = [] seen = set() for x in nums: if x in seen: continue seen.add(x) if len(heap) < k: heapq.heappush(heap, x) else: if x > heap[0]: heapq.heapreplace(heap, x) if len(heap) < k: return max(heap) return heap[0]

这个版本时间复杂度O(n log k)，空间复杂度O(n)。当k很小且固定时，三个变量法更高效；当k动态变化或者输入是流式数据时，堆的写法更通用。

5.2 堆顶为什么是“门槛”而不是“答案”

使用小顶堆找第k大，有一个非常容易混淆的点：堆顶到底是答案，还是门槛？

答案是：两者可以是同一件事。在维护过程中，堆顶是当前k个最大候选里的最小值，也就是进入前k名的门槛。新元素只有超过门槛才能进来，替换掉门槛，然后产生新的门槛。等到所有数据处理完，这个门槛同时也就是第k大的答案。

有人会问，为什么不用大根堆？因为大根堆的堆顶是当前集合里的最大值，你拿到最大值却不知道第k名是谁，也不知道该踢掉谁。只有小根堆能把“最小的阈值”暴露在堆顶，让你在常数时间内完成淘汰决策。这是 top-k 问题的一个核心考察点。

5.3 真实场景和内存权衡

这种维护 top-k 的思路在很多真实系统里都有影子：排行榜、热门关键词、游戏里的全局分数榜、日志系统里的 TOP 错误数。它们共同的特点是不能反复排序，数据源源不断进来，而且内存有限。

解法基本就是“固定大小的堆 + 辅助去重结构”。但在真实系统里，去重结构如果无限增长，内存也会爆掉。常见的妥协方案包括：只在一个时间窗口内去重，窗口过期就清空seen；或者允许少量近似误差，不严格去重，改用布隆过滤器。面试时能讲到这一层，分数通常不会低。

5.4 面试中怎么把这道题讲清楚

我建议按这个顺序回答：先复述题目并确认“不同”“不存在时返回最大值”这两个关键词；接着给出最朴素的排序方案，分析O(n log n)；然后引出三个变量法，说明用三个变量维护去重后的前三名，分析O(n)时间和O(1)空间；最后关于下界，多说一句：因为每个数字都可能影响前三名的结果，所以至少需要扫描一遍数组，O(n)已经是下界。

这套话术很顺，而且每句话都有信息量，面试官很难挑出毛病。

6. 杰瑞的每日一题：为什么这题值得刷进收藏夹

最后落到我的每日一题经验上。这道题我刷题时遇到过，也在模拟面试中给别人讲过，每次都能发现新的表达盲区。它的价值不在于让你背会一个答案，而在于训练三件事。

第一，读题要抓限定词。“不同”两个字决定了去重逻辑，“不足三个返回最大值”决定了兜底逻辑。你可以在写代码前先大声把题意复述一遍，复述不顺，说明还没读懂。

第二，写算法要讲复杂度。排序法和三个变量法的时间复杂度差了一个数量级，在面试环境里，这个差别就是你跟其他候选人的距离。能说出“为什么 O(n) 是这个问题的下界”，比单纯写出正确答案更能体现水平。

第三，边界用例要主动构造。我整理了一份我实际用来测试这道题的用例表，你可以直接拿去跑：

每次我写完这种“看起来很简单”的题，都会顺手把“三数之和”或“数据流中的第K大”再翻出来做一遍。因为它们的底层思维是相通的：要么维护固定数量的状态，要么维护一个固定大小的堆。把这三个题放在一起类比，你对整个 top-k 主题的记忆会牢固得多。

最后再分享一个小习惯：我会把每天的题解笔记分成“读题关键点”“解法演进”“避坑记录”三块。看起来费时间，但半年以后再回看这些笔记，你会发现自己对算法题的理解，早就不是当初那个只会排序取倒数第三的家伙了。