LeetCode 185. 部门工资前三高的所有员工
题目描述
题意分析
对每个部门分别找出最高的三种不同工资，返回工资属于这三档的全部员工，并输出部门名、员工名和工资。
同一档工资可以有多名员工，都必须保留，所以每个部门的结果可能超过三行；部门不足三档工资时，全部员工都符合条件。
解法：部门分区排名 + 外层筛选
核心思路
[!blue]
给每名员工计算其工资在本部门属于第几档，再筛选档位不超过 3 的行。这里需要
DENSE_RANK()：工资相同的员工名次相同，遇到下一种更低工资时，名次只增加一，不受前一档有多少员工影响。
PARTITION BY e.departmentId让排名在每个部门内独立计算，ORDER BY e.salary DESC让最高工资得到名次 1。按部门编号分区能区分不同部门，即使部门名称相同也不会混在一起。窗口函数为每一行员工增加排名，不会像聚合分组那样把同档员工合并。因此同薪员工的姓名等明细仍然保留，外层筛选
rk <= 3就能一次选出前三档的所有人。MySQL 的同层
WHERE在窗口结果产生之前处理，不能直接用它过滤刚计算出的排名。先把连接和排名放进派生表ranked，再在外层将rk当作普通列筛选。员工表与部门表通过departmentId = id连接，负责补齐输出需要的部门名称。
解题步骤
- 将
Employee与Department按部门编号连接，取得部门名、员工名和工资。- 按部门编号分区，在各分区内按工资降序计算
DENSE_RANK()，将结果命名为rk。- 将这些带排名的员工行作为派生表
ranked。- 外层保留
rk <= 3的行，只输出题目要求的Department、Employee、Salary三列，结果顺序不限。
代码实现
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。SQL 的实际开销取决于索引和执行计划，下面只估算窗口排名部分。
- 时间复杂度：各部门排序的总开销通常可按 $O(E\log(E+1))$ 估算；连接员工与部门的成本另由连接方式决定。
- 空间复杂度：窗口排序和结果缓冲通常需要 $O(E)$ 量级的辅助存储，具体是否使用临时表由执行计划决定。
关键点总结
[!green]
- 题目取的是前三种不同工资，
DENSE_RANK对应连续的工资档位。- 按部门身份分别排名，窗口计算保留每名员工的明细行。
- 先在内层产生排名，再在外层筛选排名。
易错点总结
[!yellow]
- 使用
ROW_NUMBER()：同薪员工也会得到不同编号，无法表达工资档位。- 使用
RANK()：并列人数会使后续名次跳号，第三档工资可能因此被排除。- 漏掉部门分区：会变成全公司统一排名，而不是每个部门分别选前三档。
- 按部门名称分区：名字相同的不同部门会被混为一组，应使用部门编号。
- 在同层
WHERE中过滤窗口结果：此时排名尚未计算，应先放入派生表再筛选。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 184. 部门工资最高的员工 | 中等 | 把每部门最高工资扩展到前三种不同工资，重复薪资仍应共享名次。 |
| 178. 分数排名 | 中等 | 按部门分区使用密集排名，再筛选排名不超过3，可以表达本题要求。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！