LeetCode 185. 部门工资前三高的所有员工

约 8 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 旷视
标签
数据库
目录

题目描述

✅ 185. 部门工资前三高的所有员工

题意分析

有两张表：Employee 含 id、name、salary、departmentId，Department 含 id、name。要找出每个部门里薪水排在前三高的所有员工，输出部门名、员工名、薪水三列。

题面里最容易读漏的是「前三高」的口径。它指的是不同薪水值中的前三档，而不是「薪水最高的三个人」。如果一个部门里有两个人并列第二高，那么第三档还要继续往下找——最终输出的行数可以超过 3。题目标题里的「所有员工」正是在强调这一点。

由此可以确定排名规则：并列同名次，且名次连续，不跳号。这与 178 的判定完全一致。

第二个要点是「每个部门里」。排名不是全局的，而是在部门内部独立计算：A 部门的第一名和 B 部门的第一名各算各的。这决定了排名必须按部门分区。

第三个要点是输出结构：三列的列名分别是 Department、Employee、Salary，首字母大写，与源表的列名并不相同，必须显式起别名。部门名要从 Department 表取，所以需要一次连接。

数据规模上，题目没有给出上限，但两张表是典型的事实表与维表关系，连接后按部门分区排名是标准路径。

边界包括：某个部门不足三档薪水（有几档输出几档）；某一档上有多名员工并列；以及某个部门没有员工（不会出现在结果里）。

解法：SQL 查询建模

核心思路

不用窗口函数的经典写法是关联子查询：对每名员工，统计「同部门里薪水严格高于他的不同薪水值有几个」，小于 3 就保留。这在逻辑上正确，但外层每一行都要在同部门内扫一遍并去重计数，复杂度是 $O(n^2)$ 量级，而且嵌套写法可读性很差。

瓶颈仍然是「名次」被逐行重算。而名次这个量完全可以在一次分区排序中一次性算完——这正是窗口函数的定位：为每一行附加一个与所在分区相关的统计量，同时不改变行数。

核心是把两个需求分别映射到 OVER 子句的两个部分。「在部门内部独立排名」映射为 PARTITION BY e.departmentId——它把结果集切成若干互不干扰的窗口，每个窗口内部单独编号。「按薪水从高到低定名次」映射为 ORDER BY e.salary DESC。

排名函数必须选 DENSE_RANK()。ROW_NUMBER() 会给并列的同薪员工不同名次，导致第二个 85000 被排到第 3 名、真正的第三档被挤出去；RANK() 会在并列后跳号，两人并列第 2 之后直接跳到第 4，第三档同样被漏掉。只有 DENSE_RANK() 满足「并列同名 + 名次连续」。

结构上必须先算排名、再筛名次。窗口函数在逻辑执行顺序上晚于 WHERE，所以不能直接写 WHERE DENSE_RANK() OVER (...) <= 3——那会报错。标准做法是把带排名列的查询包成一层派生表，外层再用 WHERE rk <= 3 过滤。

连接放在内层：Employee 与 Department 按 departmentId = Department.id 内连接。用内连接是因为没有对应部门的员工记录不该出现在结果里；分区键用 e.departmentId 而不是部门名，是因为 id 才是唯一标识，两个部门重名时按名字分区会把它们错误地合并。

解题步骤

  • 内层先把两张表连接起来：FROM Employee e JOIN Department d ON e.departmentId = d.id。先连接再排名，这样部门名和排名能出现在同一行上，外层直接取用。
  • 在内层的 SELECT 列表里一次性起好三个别名：d.name AS Department、e.name AS Employee、e.salary AS Salary。两张表都有 name 列，不起别名会产生歧义；别名的拼写与大小写必须与题面一致。
  • 加上排名列 DENSE_RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) AS rk。PARTITION BY 保证排名限定在部门内，ORDER BY ... DESC 保证高薪在前，DENSE_RANK 保证并列同名且不跳号。三个部件各司其职，换掉任何一个语义都会变。
  • 把内层整体包成派生表并起别名 t。派生表别名在 MySQL 里是强制的；同时这一层也解决了「窗口函数不能出现在 WHERE 中」的执行顺序问题。
  • 外层用 WHERE rk <= 3 筛出前三档，并只选出三个目标列。排名列 rk 只是中间产物，不能出现在最终输出里。

以一组具体数据走一遍。Employee 有 (1, Joe, 85000, 1)、(2, Henry, 80000, 2)、(3, Sam, 60000, 2)、(4, Max, 90000, 1)、(5, Janet, 69000, 1)、(6, Randy, 85000, 1)、(7, Will, 70000, 1)；Department 有 (1, IT)、(2, Sales)。

连接后得到七行，每行带上部门名。接着按 departmentId 分区计算排名。

IT 部门（departmentId = 1）有五行，薪水降序是 90000、85000、85000、70000、69000。DENSE_RANK 依次赋值：Max 的 90000 是第 1 档；Joe 与 Randy 的 85000 并列第 2 档；Will 的 70000 是第 3 档；Janet 的 69000 是第 4 档。

Sales 部门（departmentId = 2）有两行，薪水降序是 80000、60000。Henry 是第 1 档，Sam 是第 2 档。

外层筛 rk <= 3：IT 部门保留 Max、Joe、Randy、Will 四行——注意输出了四个人，正是「前三档」而非「前三人」；Janet 因为第 4 档被剔除。Sales 部门两行全部保留，因为它只有两档。

最终输出六行：(IT, Max, 90000)、(IT, Joe, 85000)、(IT, Randy, 85000)、(IT, Will, 70000)、(Sales, Henry, 80000)、(Sales, Sam, 60000)。

若把 DENSE_RANK() 换成 ROW_NUMBER()，IT 部门的五行会被编成 1 到 5，rk <= 3 只留下 Max、Joe、Randy 三行，Will 被错误地挤掉；若换成 RANK()，两个 85000 并列第 2 之后 Will 直接跳到第 4 名，同样被挤掉。两种错法都会丢失 (IT, Will, 70000) 这一行。

代码实现

SELECT Department, Employee, Salary
FROM (
    SELECT
        d.name AS Department,
        e.name AS Employee,
        e.salary AS Salary,
        -- 按部门分区、按薪水降序，DENSE_RANK 保证并列同名且名次连续。
        DENSE_RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) AS rk
    FROM Employee e
    JOIN Department d
    ON e.departmentId = d.id
) AS ranked
-- 窗口函数不能写在同层 WHERE 中，先放进派生表再过滤。
WHERE rk <= 3;

复杂度分析

  • 时间复杂度：以员工数 $E$ 为主，分区排序通常是 $O(E \log E)$，排名与过滤是 $O(E)$；连接代价取决于索引和执行计划。
  • 空间复杂度：最坏 $O(E)$，用于排序和窗口执行缓冲；具体是否物化派生结果由数据库决定。

关键点总结

  • 「每组前 N 名」是 SQL 面试的高频模式，标准解法固定为「窗口排名 + 派生表 + 外层筛名次」三段式。记住这个骨架，剩下的只是把分区键、排序键和 N 填进去。
  • 排名函数的选择由题面对并列的约定决定。本题要求「前三档且包含全部并列者」，只有 DENSE_RANK() 成立；若题目改成「每组恰好三行」，则该用 ROW_NUMBER()。这个辨析要能当场说清。
  • PARTITION BY 是「分组但不聚合」——它切分窗口却保留每一行明细，与 GROUP BY 把多行压成一行有本质区别。需要「保留明细同时带上组内统计量」时就该用它。
  • 窗口函数在逻辑上晚于 WHERE 求值，所以对排名的过滤必须放到外层。这条执行顺序是写窗口函数时最常撞的语法墙。
  • 分区键要选唯一标识而非展示名。用 departmentId 而不是部门名分区，能在两个部门重名时依然正确。
  • 面试表达顺序应是：先确认「前三档而非前三人」，再说明按部门分区、按工资降序做稠密排名，最后解释窗口结果为何必须在外层过滤。

易错点总结

  • 错误写法：用 ROW_NUMBER() 代替 DENSE_RANK()。用例：IT 部门薪水为 90000、85000、85000、70000 → 四行被编成 1、2、3、4，rk <= 3 把 70000 的 Will 挤掉，正确答案应包含他。
  • 错误写法：用 RANK() 代替 DENSE_RANK()。用例：同上数据 → 两个 85000 并列第 2 后直接跳到第 4，Will 的名次是 4 被剔除，正确答案应包含他。
  • 错误写法：直接写 WHERE DENSE_RANK() OVER (...) <= 3。用例：任意数据 → 数据库报「Window function is allowed only in SELECT list and ORDER BY clause」，查询无法执行。
  • 错误写法：OVER 子句里漏掉 PARTITION BY。用例：IT 与 Sales 两个部门 → 排名变成全局的，Sales 的 60000 在全表里排到第 5 档被剔除，正确答案应输出它。
  • 错误写法：PARTITION BY d.name 用部门名分区。用例：两个 id 不同但同名的部门 → 它们的员工被合并进同一个窗口共同排名，两边各自的第三档都可能被挤掉。
  • 错误写法：ORDER BY e.salary 漏掉 DESC。用例：Sales 部门薪水为 80000、60000 → 60000 被排成第 1 档，筛选保留的是最低的三档，与题意完全相反。
  • 错误写法：派生表不起别名。MySQL 要求每个派生表都有别名，否则查询直接报错。
  • 错误写法：内层不给 d.name 与 e.name 起别名。用例：任意数据 → 两个 name 列同名，外层无法区分该取哪个，报列名歧义错误。
  • 错误写法：把排名列 rk 也选进最终输出。用例：任意数据 → 输出多出一列，与题目要求的三列结构不符，判定失败。

相似题目

题目 难度 考察点
184. 部门工资最高的员工 中等 N 固定为 1，可用 IN 配对分组最大值绕过窗口函数，是本题的简化版
178. 分数排名 中等 同样用 DENSE_RANK 但不分区，排名本身就是输出列而非筛选条件
177. 第N高的薪水 中等 只取单个名次且要求返回标量，用 DISTINCT 加 LIMIT OFFSET 更直接
176. 第二高的薪水 中等 名次固定为 2，重点在于无解时必须返回 NULL 而非零行
181. 超过经理收入的员工 简单 自连接表达同表内的层级关系，考点是别名的角色分配而非排名
569. 员工薪水中位数 困难 分组内取中间名次，要同时处理奇偶行数，比取前 N 名多一层数学讨论
1341. 电影评分 中等 两个「组内取第一」的子问题拼接输出，还要处理并列时按名称字典序取最小
1280. 学生们参加各科测试的次数 简单 用交叉连接构造完整骨架再左连接补数，展示与本题相反的「保留无匹配」需求