LeetCode 177. 第N高的薪水

2022-02-11 HGNULB 约 6 分钟

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

分类

题目描述

✅ 177. 第N高的薪水

题意分析

Employee 表里每行是一名员工的 id 与 salary。要写一个接受参数 N 的函数，返回薪水表中第 N 高的薪水；不存在就返回 NULL。

「第 N 高」在这里指的是去重之后的第 N 高。如果三个人都拿 100、两个人拿 90，那么第一高是 100、第二高是 90——不是「第二高也是 100」。题面对并列的这条约定，是整道题第一个必须处理的语义点。

第二个语义点是结果集必须恰好一行一列，列名固定为 getNthHighestSalary(N) 的返回值形态。所以不能返回一个多行结果，也不能返回一个空结果集——数据不足时必须是 NULL 这个值，而不是零行。

第三个是参数 N 的语义：它是从 1 开始计数的序号，而 SQL 的偏移量是从 0 开始的，两者之间恒定差一。这个转换必须显式完成。

边界包括：N 大于不同薪水的个数（返回 NULL）；表为空（返回 NULL）；N = 1（退化成求最大值）；以及大量并列薪水的情形。

解法：SQL 查询建模

核心思路

最直觉的写法是「按薪水降序排序，取第 N 行」。它在思路上是对的，但直接落地会踩三个坑：并列薪水会占掉多个行位，导致序号错位；偏移量与序号差一；数据不足时会返回零行而不是 NULL。

三个坑对应三步修正，正好构成了完整解法。

第一步用 DISTINCT 把并列压平。去重之后每个薪水值只占一行，行序号就与「第几高」严格对齐了。这一步不能用 GROUP BY salary 之外的任何等价物草率替换——真正要表达的是「取值集合」，DISTINCT 是最直白的写法。

第二步把序号转成偏移量。LIMIT offset, row_count 的第一个参数从 0 开始，要拿第 N 高就得跳过前 N - 1 行。MySQL 的存储程序允许 LIMIT 使用整型例程参数或局部变量，所以先执行 SET N = N - 1，再写 LIMIT N, 1 即可。

第三步解决空结果。关键在于标量子查询的语义：当一个子查询被放在 RETURN (...) 里作为单个值使用时，若它没有返回任何行，整个表达式的求值结果就是 NULL，而不是报错、也不是空集。这正好免费满足了「数据不足返回 NULL」的要求，不需要写 IFNULL 或任何显式判空。

这里不需要派生表：MySQL 的限制针对 LIMIT 与 IN/ALL/ANY/SOME 等特定子查询组合，并不禁止标量子查询中的 ORDER BY ... LIMIT。直接返回这一条标量查询，语义和输出形态都最清楚。

解题步骤

先把参数从「序号」改写成「偏移量」，即 SET N = N - 1。之所以在函数体开头就改，是为了让后面的 SQL 里只出现一个变量、语义单一，不必在两种计数体系之间来回换算。

查询去重后的薪水并降序排列：SELECT DISTINCT salary FROM Employee ORDER BY salary DESC。DISTINCT 负责压平并列，DESC 负责让「第 1 行」就是最高薪。

加上 LIMIT N, 1 定位目标行。先跳过 N 行（此时 N 已是偏移量），再取 1 行。LIMIT 必须写在 ORDER BY 之后，定位的才是降序结果中的目标名次。

整体作为标量子查询由 RETURN 返回。零行时自动求值为 NULL，恰好覆盖「不足 N 个不同薪水」的情形，无需额外分支。

以一张具体的表走一遍：Employee 中有 (1, 100)、(2, 200)、(3, 300)、(4, 200) 四行，调用 getNthHighestSalary(2)。

函数体先执行 SET N = N - 1，N 变成 1。SELECT DISTINCT salary FROM Employee ORDER BY salary DESC 得到三行：300、200、100——注意两个 200 已被压成一行，这正是 DISTINCT 的作用。接着 LIMIT 1, 1 跳过第一行 300、取出第二行 200，标量子查询返回 200，正确。

再调用 getNthHighestSalary(4)。N 变成 3，去重后仍只有三行，LIMIT 3, 1 返回零行；标量子查询的值因此是 NULL，正确。

若漏掉 DISTINCT，同一张表调用 getNthHighestSalary(3) 时，偏移量为 2：查询只跳过 300 和第一个 200，随后取到第二个 200；正确的第三高应是 100。重复薪资占用了额外行位，这正是必须先去重的原因。

代码实现

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    -- 序号从 1 起、偏移量从 0 起，先把两者对齐。
    SET N = N - 1;
    RETURN (
        -- DISTINCT 压平并列；N 已转换为从 0 开始的偏移量。
        SELECT DISTINCT salary
        FROM Employee
        ORDER BY salary DESC
        LIMIT N, 1
    );
END

复杂度分析

时间复杂度：没有可用索引时，需要扫描、去重并排序，通常记为 $O(n \log n)$。若 salary 上有合适索引，可按薪水倒序扫描；实际读取量取决于凑出前 N 个不同薪水需要跨过多少行，最坏仍为 $O(n)$。

空间复杂度：取决于去重与排序所需的中间结果，最坏是 $O(d)$，$d$ 为不同薪水的个数。

关键点总结

「第 N 高 / 第 N 大」类题目要先确认并列如何计数。本题按去重后计数，所以 DISTINCT 是语义必需而非性能优化；若题目改成「并列共享名次且名次连续」，就该换成 DENSE_RANK()。

序号与偏移量之间恒定差一，把转换集中在一处（这里是函数开头的 SET）比在 SQL 里到处写 N - 1 更不容易错。

标量子查询在零行时求值为 NULL，这是把「无解」翻译成「返回空值」的最省事写法。识别出这条语义，就能省掉 IFNULL、CASE 等一整套分支。

MySQL 存储程序允许 LIMIT 引用整型参数或局部变量；这里的 N 已在函数体内转换成合法的非负偏移量。

易错点总结

错误写法：省略 DISTINCT。用例：表中有 (1, 200)、(2, 200)、(3, 100)，调用 N = 2 → 跳过第一个 200 后取到第二个 200，返回 200，正确答案是 100。

错误写法：LIMIT 1 OFFSET N 中直接用未减一的 N。用例：同上表，调用 N = 1 → 跳过最高的 200 取到 100，返回 100，正确答案是 200。

错误写法：把 SET N = N - 1 写在 RETURN 之后。用例：任意调用 → RETURN 一执行函数就结束，赋值语句永远不会生效，偏移量始终等于序号，全部结果错位一名。

错误写法：用 IFNULL(..., 0) 兜底无解情形。用例：表中只有两个不同薪水，调用 N = 5 → 返回 0，正确答案是 NULL；0 是一个合法薪水值，会被下游误解为「有人拿 0 元」。

错误写法：ORDER BY 写在 LIMIT 之后。用例：任意调用 → 语法错误；ORDER BY 必须先于 LIMIT，否则跳过的是未定义顺序的行。

错误写法：漏写 DESC。用例：表中有 100、200、300，调用 N = 1 → 升序排列后取第一行得到 100，正确答案是 300。

错误写法：用 SELECT MAX(salary) FROM Employee WHERE salary < (SELECT MAX(salary) ...) 这类嵌套来求第 N 高。用例：N = 3 → 需要嵌套三层，N 是运行时参数时根本无法写出固定层数的 SQL，方案不可行。

错误写法：用 ROW_NUMBER() 打名次后筛 = N。用例：表中有 (1, 200)、(2, 200)、(3, 100)，调用 N = 2 → ROW_NUMBER() 给两个 200 分别打 1 和 2，返回 200，正确答案是 100；并列必须用 DENSE_RANK()。

相似题目

题目	难度	考察点
176. 第二高的薪水	中等	`N` 固定为 2，可用嵌套子查询硬写，是本题参数化之前的特例
178. 分数排名	中等	要输出全部行的名次而非某一行，`DENSE_RANK()` 从筛选工具变成输出列
184. 部门工资最高的员工	中等	分组求最值并保留明细，考点是分组内比较与连接维表
185. 部门工资前三高的所有员工	困难	分组内取前 N 名，必须用 `PARTITION BY` 配合窗口排名，`LIMIT` 无能为力
182. 查找重复的电子邮箱	简单	靠 `GROUP BY` 加 `HAVING` 做分组过滤，展示聚合筛选与行筛选的分工
569. 员工薪水中位数	困难	同样按名次定位，但要同时处理奇偶行数，需要正反两次排名取交集
1204. 最后一个能进入巴士的人	中等	也要在排序后定位「某一行」，但定位条件是累计和的阈值而非固定偏移量
1341. 电影评分	中等	两段各自排序取首行再合并，考察多结果集拼接与并列时的次级排序规则