LeetCode 176. 第二高的薪水

2023-10-22 HGNULB 约 7 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 176. 第二高的薪水

题意分析

Employee 表有 id 与 salary 两列。要求查出第二高的不同薪水，输出单列 SecondHighestSalary。若不存在第二高（表为空，或所有人薪水相同），必须返回一行值为 null 的结果，而不是零行。

「不同薪水」这四个字是全题第一个关卡：三个人薪水分别是 $200, 200, 100$ 时，第二高是 $100$ 而不是 $200$。排名建立在去重后的薪水值上，与员工人数无关。

「不存在时返回 null 而非空集」是第二个关卡，也是这道题被定为中等而非简单的唯一原因。一个朴素的 ORDER BY ... LIMIT 1 OFFSET 1 在没有第二行时返回的是零行，而判题要求的是一行一列且该列为 null。这两者在 SQL 里是完全不同的结果集，必须显式转换。

边界共三类：表为空；表中只有一条记录；表中多条记录但薪水全部相同。这三种都应当返回一行 null。

解法：SQL 查询建模

核心思路

最直接的写法是 SELECT MAX(salary) FROM Employee WHERE salary < (SELECT MAX(salary) FROM Employee)，它利用了聚合函数 MAX 在空集上返回 null 的特性，天然满足「无解返回 null」。但它只适用于「第二高」，一旦题目改成第 $N$ 高就要嵌套 $N$ 层，不可扩展。

更通用的思路是排序加偏移：把薪水去重后降序排列，跳过第一行取第二行。这就是 SELECT DISTINCT salary FROM Employee ORDER BY salary DESC LIMIT 1 OFFSET 1。DISTINCT 负责「不同薪水」这一条，OFFSET 1 负责「第二」这一条，改成第 $N$ 高只需把偏移量换成 $N-1$。

但它有一个致命缺口：当去重后的薪水不足两个时，这条查询返回零行。判题期望的却是一行 null。

补上缺口的关键在于一条 SQL 语义：把一个查询写成标量子查询（放在 SELECT 列表里、括号包裹、保证至多返回一行一列）时，若它返回零行，其取值就是 null 而不是「无结果」。也就是说，把上面那条查询整体嵌进外层 SELECT 的列位置，零行会自动被求值成 null，而外层 SELECT 不带 FROM，无论如何都会产出恰好一行。这一步「零行转 null」的转换，正是本题的题眼。

最后套一层 IFNULL(..., NULL) 并用 AS SecondHighestSalary 命名。IFNULL 在这里其实是恒等的（null 换成 null），保留它是为了把「结果可能为空」这个意图显式写在代码里，同时在换成 IFNULL(..., 0) 这类变体需求时只需改一处。

解题步骤

内层先写 SELECT DISTINCT salary FROM Employee。DISTINCT 必须加：题目问的是第二高的不同薪水，$200, 200, 100$ 这样的数据若不去重，偏移一行拿到的仍是 $200$。

加 ORDER BY salary DESC，把去重后的薪水按从高到低排列，使得「第 $k$ 高」等价于「第 $k$ 行」。降序不能写成升序，否则拿到的是第二低。

加 LIMIT 1 OFFSET 1：OFFSET 1 跳过最高的那一行，LIMIT 1 只取紧随其后的一行。这个组合把「第二」这个序号翻译成了行偏移，推广到第 $N$ 高就是 OFFSET N-1。

把整条内层查询用括号包起来，放进一个不带 FROM 的外层 SELECT 的列位置。这是唯一能把「零行」变成「一行 null」的手段：外层没有 FROM 所以必定输出一行；内层作为标量子查询在零行时求值为 null。若不套这一层，空表场景下返回零行，判题不通过。

外层套 IFNULL(..., NULL) 并用 AS SecondHighestSalary 指定列名。列名必须与题目要求逐字一致，SQL 题的判题是按列名匹配的。

以三组数据各走一遍：

数据一 Employee = [(1, 100), (2, 200), (3, 300)]：内层 DISTINCT 得 ${100, 200, 300}$，降序排为 $300, 200, 100$；OFFSET 1 跳过 $300$，LIMIT 1 取到 $200$。内层返回一行值 $200$，作为标量即 $200$，IFNULL(200, NULL) 仍是 $200$。输出一行 SecondHighestSalary = 200。
数据二 Employee = [(1, 100)]：内层 DISTINCT 得 ${100}$，降序只有一行；OFFSET 1 跳过它之后已无数据，LIMIT 1 取不到任何行，内层返回零行。作为标量子查询求值为 null，IFNULL(null, NULL) 是 null。外层无 FROM，仍输出一行，SecondHighestSalary = null。这一行正是判题要的答案，也是不套外层就会丢失的那一行。
数据三 Employee = [(1, 200), (2, 200)]：DISTINCT 把两条压成一个值 $200$，之后与数据二完全一样，输出 null。如果漏写 DISTINCT，降序两行都是 $200$，OFFSET 1 会取到第二个 $200$，错误地输出 $200$。

代码实现

SELECT IFNULL(
    (
        -- 内层作为标量子查询：取不到行时整体求值为 null，
        -- 外层不带 FROM 保证无论如何都输出恰好一行。
        SELECT DISTINCT salary
        FROM Employee
        ORDER BY salary DESC
        LIMIT 1 OFFSET 1
    ),
    NULL
) AS SecondHighestSalary;

复杂度分析

时间复杂度：$O(n \log n)$，$n$ 为 Employee 的行数。主要成本是 DISTINCT 的去重与 ORDER BY 的排序，两者通常合并为一次排序或哈希去重加排序；若 salary 上建有索引，优化器可以直接反向扫描索引并在取到第二个不同值后停止，降到 $O(\log n)$ 级别。外层的标量子查询只执行一次。

空间复杂度：$O(d)$，$d$ 为不同薪水的个数。去重需要一个哈希表或排序缓冲区来容纳这些值；LIMIT 1 OFFSET 1 使得实际物化的结果只有一行，最终结果集恒为一行一列。

关键点总结

SQL 里「零行」与「一行 null」是两种不同的结果，题目要哪种必须看清。把查询包成不带 FROM 的外层 SELECT 的标量子查询，是把前者转成后者的标准手法；反过来，聚合函数（MAX、MIN）在空集上直接返回 null，也能达到同样效果。

涉及「第 $k$ 大/小」时先确认排名是建立在原始行上还是去重值上。前者用 LIMIT/OFFSET 或 ROW_NUMBER()，后者必须先 DISTINCT 或改用 DENSE_RANK()。

ORDER BY 配 LIMIT n OFFSET m 是把「序号」翻译成「行位置」的通用桥梁，比嵌套 MAX 更容易推广到第 $N$ 高。

输出列名要与题面逐字一致，SQL 判题按列名匹配，AS 不可省。

面试视角：面试官最想听的是你主动指出「没有第二高时要返回 null 而不是空集」，并说清标量子查询的这条语义。接着大概率追问两件事——「改成第 $N$ 高怎么办」（把 OFFSET 1 换成 OFFSET N-1，注意 MySQL 的 LIMIT 不接受表达式，要先算进变量）；「有并列时 DENSE_RANK() 和 RANK() 有什么区别」（前者名次连续、正好对应「不同薪水」的语义，后者会跳号）。

易错点总结

漏写 DISTINCT：Employee = [(1, 200), (2, 200), (3, 100)] 时降序为 $200, 200, 100$，偏移一行取到第二个 $200$，输出 $200$，正确答案是 $100$。

不套外层 SELECT 而直接返回内层查询：Employee = [(1, 100)] 时返回零行，判题期望一行 null，直接判错。

ORDER BY 漏写 DESC：Employee = [(1, 100), (2, 200), (3, 300), (4, 400)] 升序排为 $100, 200, 300, 400$，偏移一行取到 $200$，即第二低的薪水，正确答案是 $300$。

OFFSET 写成 $2$：Employee = [(1, 100), (2, 200), (3, 300)] 会跳过 $300$ 和 $200$ 取到 $100$，输出的是第三高。

LIMIT 2 而不加 OFFSET：返回 $300$ 和 $200$ 两行，而外层标量子查询要求至多一行，数据库直接报「子查询返回多行」的错误。

列名写成 salary 或 secondHighestSalary：判题按列名精确匹配，大小写或拼写不符直接算错。

用 MAX(salary) WHERE salary < MAX(salary) 却把内层写成同一层聚合：SELECT MAX(salary) FROM Employee WHERE salary < MAX(salary) 在 WHERE 中使用聚合函数，MySQL 直接报语法错误，必须写成子查询。

用 LIMIT 1, 1 时把两个参数顺序记反：MySQL 中 LIMIT 1, 1 是「偏移 1 取 1 行」，若写成 LIMIT 1 OFFSET 1 之外的方言（如 LIMIT 1, 2）会取到两行触发多行错误。

用 ROW_NUMBER() 而非 DENSE_RANK() 做排名：Employee = [(1, 200), (2, 200), (3, 100)] 时 ROW_NUMBER 给两个 $200$ 分别编号 1 和 2，取第 2 名得到 $200$，正确答案是 $100$。

用 IFNULL 包住的是外层而非内层：写成 IFNULL(salary, NULL) 放进内层查询里，零行时内层仍返回零行，IFNULL 根本没有机会被求值。

相似题目

题目	难度	考察点
177. 第N高的薪水	中等	本题的参数化推广，需写成函数并处理 `LIMIT` 不接受表达式的限制
178. 分数排名	中等	要求并列同名次且名次连续，正是 `DENSE_RANK()` 的定义场景
184. 部门工资最高的员工	中等	排名从全表变成分组内，需 `PARTITION BY` 或关联子查询，且并列全部保留
185. 部门工资前三高的所有员工	困难	分组内取前三个不同薪水，`DENSE_RANK() <= 3` 是标准解
175. 组合两个表	简单	考的是左连接保留无匹配行并自动补 `null`，与本题的空值语义互为镜像
182. 查找重复的电子邮箱	简单	分组后用 `HAVING COUNT(*) > 1` 过滤，考聚合与过滤时机的区别
196. 删除重复的电子邮箱	简单	写的是 `DELETE` 而非 `SELECT`，需处理 MySQL 不能直接子查询同表的限制
181. 超过经理收入的员工	简单	同表自连接比较两行的字段，考连接条件的书写