0177. Nth Highest Salary

题目信息

题号:
  1. 第 N 高的薪水

难度:

Medium

主题:

Database、存储函数、去重、排序分页

原题:

LeetCode 0177

重点:

先把员工行压缩成不同薪资等级,再把一基名次转换为零基偏移并保留 NULL 合同

题目重述

Employee(id, salary) 表保存员工及薪资。实现 MySQL 函数 getNthHighestSalary(N),返回第 N 高的 不同薪资值。

N 从 1 开始:N = 1 表示最高薪资。相同薪资只占一个名次;若不同薪资等级不足 N 个,函数返回 NULL。

自建示例

Employee:
id | salary
1  | 7200
2  | 5400
3  | 7200
4  | 4600

getNthHighestSalary(2) = 5400
getNthHighestSalary(4) = NULL

不同薪资降序为 7200、5400、4600;重复的 7200 只占第一个名次。
Employee:
id | salary
1  | 3000
2  | 3000

getNthHighestSalary(1) = 3000
getNthHighestSalary(2) = NULL

SQL 实现

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    SET N = N - 1;

    RETURN (
        SELECT DISTINCT salary
        FROM Employee
        ORDER BY salary DESC
        LIMIT N, 1
    );
END

题解

原始行排名混入了重复员工

若直接按 salary DESC 排序员工行,第 N 行表示第 N 名员工,而不是第 N 个薪资等级。示例的前两行都可能是 7200,于是 N = 2 会错误返回最高薪资。

窗口函数也必须选择正确语义:直接对员工行使用 ROW_NUMBER 会给重复薪资不同序号; RANK 会在重复组后留下名次空洞。可以使用 DENSE_RANK,但本题只需返回一个值, 先 DISTINCT 再定位更直接。

先压缩成真正的搜索序列

SELECT DISTINCT salary 把任意数量的员工行压缩为不同薪资等级。随后 ORDER BY salary DESC 将这些等级排列为题目定义的次序:

位置:1     2     3
薪资:7200  5400  4600

去重必须发生在取位置之前。若先限制员工行再去重,重复的高薪行可能占满窗口,使真正的 第 N 个等级从候选中消失。

一基名次到零基偏移

SQL LIMIT offset, row_count 的偏移从 0 开始,而函数参数 N 从 1 开始。因此进入 查询前执行 SET N = N - 1:

第 1 高 -> 跳过 0 行
第 2 高 -> 跳过 1 行
第 N 高 -> 跳过 N - 1 行

LIMIT N, 1 随后只读取目标位置的一行。先减一再传给 LIMIT 的顺序直接编码了两种 下标体系的转换;题目保证传入正整数,因此不会产生负偏移。

函数为何能返回 NULL

RETURN (...) 中的括号把查询作为标量子查询使用:

  • 找到目标薪资时,子查询恰好返回一个值;

  • 不同薪资不足 N 个时,偏移后没有行,标量子查询的结果为 NULL。

因此无需返回字符串 "NULL",也无需用 0 作为哨兵。0 可能是合法薪资,而 SQL 空值 正好表示“第 N 个等级不存在”。LIMIT 保证子查询最多一行,不会违反标量上下文。

具体走读

对 7200、5400、7200、4600 且 N = 2:

  1. DISTINCT 得到 7200、5400、4600;

  2. 降序排列后顺序不变;

  3. 函数把 N 从 2 改为偏移 1,跳过 7200,读取一行 5400 并返回。

若 N = 4,跳过三个已有等级后没有剩余行,标量子查询返回 NULL。整个过程不会因 7200 对应两个员工而改变偏移量。

与固定第二高查询的关系

固定查询第二高时,可以把它写成“小于最高薪资的最大值”;推广到任意 N 后,反复 嵌套 MAX 会随 N 增加查询层数。去重、排序、偏移一次性建立完整的不同薪资顺序, 让 N 只影响跳过多少行,结构保持不变。

执行代价

逻辑工作包括去重、降序排序和读取一个偏移位置。无可用索引时,数据库通常需要扫描 Employee 并对不同薪资排序;设员工数为 m、不同薪资数为 u,排序上界为 O(u log u)。薪资索引、流式去重及优化器选择可能降低实际代价,但不会改变“先形成 不同等级,再按降序取零基偏移”的查询语义。