LeetCode 184. 部门工资最高的员工

约 8 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动
标签
数据库
目录

题目描述

✅ 184. 部门工资最高的员工

题意分析

两张表：Employee 有 id、name、salary、departmentId，Department 有 id、name。要找出每个部门里工资最高的员工，输出三列 Department、Employee、Salary。

第一个关卡是并列：如果一个部门有多名员工并列最高工资，题目要求他们全部输出，而不是任选一个。这直接排除了「按部门分组后取一行」的写法——GROUP BY departmentId 之后每组只剩一行，无法带出多名并列者，更不能顺带把 name 拼出来（name 不在分组键里，选出来的是不确定的任意值）。

第二个关卡是输出粒度：结果的一行对应一名员工，而「部门最高工资」是一个部门级别的聚合量。两个粒度不同的东西要放进同一行，就必须先把聚合结果算出来，再连接回员工明细。这正是所有「组内取极值并保留明细」类题目的通用结构。

第三个关卡是列名与来源：Department 与 Employee 两张表都有 name 列，写查询时必须用别名限定，且输出列名要与题目逐字一致。

边界有两处：某个部门在 Employee 中一名员工都没有时，该部门不应出现在结果里（内连接天然满足）；Employee.departmentId 按题意总能在 Department 中找到对应，不需要处理悬挂外键。

解法：SQL 查询建模

核心思路

一个直觉写法是 SELECT departmentId, name, MAX(salary) FROM Employee GROUP BY departmentId。它是错的，而且错得很典型：name 既不在 GROUP BY 里也不在聚合函数里，严格模式下 MySQL 直接报错，宽松模式下会返回组内任意一行的 name，与 MAX(salary) 毫无关联。聚合会把明细行压扁，压扁之后就再也拿不回「是谁拿了这个最高工资」。

正确的思路是把问题拆成两步、两个粒度：先在部门粒度上算出每个部门的最高工资，再回到员工粒度上筛出工资恰好等于所属部门最高值的那些人。前者是聚合，后者是过滤，两者用连接缝合。

于是核心结构是：用一个子查询 m 产出「部门 → 最高工资」的映射表，再把它按 (departmentId, salary) 两个字段同时连接回 Employee。连接条件必须是两个字段的合取——只连 departmentId 会把部门内所有员工都保留下来，只连 salary 会把「工资等于其他部门最高值」的人误选进来。两个条件一起，才精确刻画出「此人的工资就是他自己部门的最高值」。

用连接而不是 WHERE salary = (SELECT MAX(...) WHERE departmentId = e.departmentId) 这种关联子查询，好处是并列者自然全部保留（连接是多对一，一个最高值能匹配上多名并列员工），且优化器通常能把子查询物化一次而不是逐行执行。

最后再连接 Department 表把部门 id 换成部门名。三张表（其中一张是派生表）的连接顺序不影响结果，因为全是内连接。

解题步骤

  • 先写出派生表 m：SELECT departmentId, MAX(salary) AS max_salary FROM Employee GROUP BY departmentId。这一步把粒度从员工降到部门，产出的每一行是「某部门的最高工资是多少」。这里可以放心用 MAX，因为 SELECT 列表中只有分组键和聚合函数，没有粒度冲突。
  • 把 m 按 m.departmentId = e.departmentId AND m.max_salary = e.salary 连回 Employee e。两个条件缺一不可：前者定位到「同一个部门」，后者要求「工资正好是那个最高值」。这个连接是一对多的——一个 m 行可以匹配多名并列员工，于是并列者被自动全部保留，不需要任何额外处理。
  • 再把 Department d 按 d.id = e.departmentId 连进来，目的只是把部门 id 翻译成部门名。用内连接是安全的，因为题目保证 departmentId 都有效；即便有悬挂外键，内连接丢弃它们也符合「部门名未知则不输出」的常识。
  • SELECT 三列并逐一起别名：d.name AS Department、e.name AS Employee、e.salary AS Salary。两张表都有 name 列，不加表别名限定会报「列名歧义」；输出别名必须与题目要求逐字一致，SQL 判题按列名匹配。
  • 不需要 DISTINCT。连接结果的每一行对应一名唯一的员工，不会重复；若加了 DISTINCT，反而会把「同一部门内同名同薪的两名不同员工」错误地合并成一行。

以 Employee = [(1, 'Joe', 70000, 1), (2, 'Jim', 90000, 1), (3, 'Henry', 80000, 2), (4, 'Sam', 60000, 2), (5, 'Max', 90000, 1)]、Department = [(1, 'IT'), (2, 'Sales')] 走一遍：

派生表 m：部门 1 的员工工资有 $70000, 90000, 90000$，最大是 $90000$；部门 2 有 $80000, 60000$，最大是 $80000$。所以 m = [(1, 90000), (2, 80000)]。
连接 m 与 Employee：Joe（部门 1，$70000$）——部门匹配但工资 $70000 \ne 90000$，被过滤；Jim（部门 1，$90000$）——两条件全中，保留；Henry（部门 2，$80000$）——两条件全中，保留；Sam（部门 2，$60000$）——工资不等，过滤；Max（部门 1，$90000$）——两条件全中，保留。
此时剩下 Jim、Henry、Max 三行。注意 Jim 与 Max 同为部门 1 的最高工资，两人都被保留——这正是用连接而非分组的价值。
连接 Department：Jim 与 Max 归到 IT，Henry 归到 Sales。
输出三行：('IT', 'Jim', 90000)、('Sales', 'Henry', 80000)、('IT', 'Max', 90000)。

反过来验证一下条件缺失的后果：若连接条件只写 m.max_salary = e.salary，那么部门 2 里若有人工资恰为 $90000$（部门 1 的最高值），他也会被匹配上部门 1 的那行 m 而被错误选出。

代码实现

SELECT
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
FROM Employee e
JOIN Department d ON d.id = e.departmentId
-- 先在部门粒度算出每个部门的最高工资，再按「部门 + 工资」双条件连回员工明细，
-- 连接是一对多，因此同部门的多名并列最高者会被全部保留。
JOIN (
    SELECT departmentId, MAX(salary) AS max_salary
    FROM Employee
    GROUP BY departmentId
) m ON m.departmentId = e.departmentId AND m.max_salary = e.salary;

复杂度分析

  • 时间复杂度：$O(n + m)$ 到 $O(n \log n)$，$n$ 为 Employee 行数、$m$ 为 Department 行数。派生表需要对 Employee 做一次分组聚合，哈希分组是 $O(n)$、排序分组是 $O(n \log n)$；随后两次等值连接，若 departmentId 与 Department.id 上有索引则每行 $O(\log)$ 探查，走哈希连接则接近线性。派生表本身只有 $m$ 行，构建它的哈希表代价很小。
  • 空间复杂度：$O(m + r)$，$m$ 为部门数（派生表与其哈希表的规模），$r$ 为结果行数。派生表的行数由部门数决定而非员工数，所以即便员工上百万，中间结果依然很小——这也是先聚合再连接比逐行关联子查询更省资源的原因。

关键点总结

  • 「组内取极值并保留明细」的标准结构是两步：先在组粒度聚合出极值，再按「组键 + 极值」双条件连回明细表。直接 GROUP BY 后 SELECT 非分组列是这类题最常见的错误，因为聚合已经把明细压扁了。
  • 判断要不要保留并列：题目说「所有」就必须用连接或 RANK()/DENSE_RANK()；说「任意一个」才可以用 ROW_NUMBER() = 1 或 LIMIT 1。这个区别决定了整条查询的写法。
  • 连接条件要覆盖「组」和「值」两个维度。只连值会跨组误匹配，只连组会失去过滤作用；写多表连接时逐条问自己「这个条件排除了什么」。
  • 同名列必须用表别名限定。两张表都有 name 时不加限定会直接报歧义错误，而输出别名又必须与题面逐字一致，这两处是 SQL 题的固定失分点。
  • 面试视角：面试官会先看你能否指出 GROUP BY 直接选 name 的错误，再问「有并列怎么办」。答完连接方案后，多半会追问「用窗口函数怎么写」——要能给出 DENSE_RANK() OVER (PARTITION BY departmentId ORDER BY salary DESC) = 1 这个更简洁的等价写法，并说明为什么用 DENSE_RANK 或 RANK 而不是 ROW_NUMBER（后者会把并列者只留一个）。再追问「前三高」就自然过渡到 185 题。

易错点总结

  • 直接 GROUP BY departmentId 并 SELECT name, MAX(salary)：Employee 中部门 1 有 Joe($70000$) 和 Jim($90000$) 时，name 不在分组键里，MySQL 严格模式报错，宽松模式可能输出 ('Joe', 90000) 这种张冠李戴的组合。
  • 连接条件只写 m.max_salary = e.salary：部门 2 若有人工资也是 $90000$（部门 1 的最高值），他会被匹配上部门 1 的那行 m 而被错误选出，即使他在自己部门里并非最高。
  • 连接条件只写 m.departmentId = e.departmentId：Joe($70000$) 与 Sam($60000$) 这些非最高工资的员工全部被保留，结果集变成全部员工。
  • 用 ROW_NUMBER() OVER (PARTITION BY departmentId ORDER BY salary DESC) = 1：Jim 与 Max 并列 $90000$ 时只会保留其中一人，正确答案要求两人都输出。
  • 输出列名写成 d.name、e.name、salary 而不起别名：判题按 Department、Employee、Salary 三个列名匹配，不起别名直接判错；且两个 name 同名会导致结果列重名。
  • SELECT name 不加表前缀：Department 与 Employee 都有 name 列，数据库直接报「column 'name' in field list is ambiguous」。
  • 把 JOIN Department 写成 Department.id = Employee.id：连接的是员工 id 与部门 id，Employee 中 id = 1 的 Joe 会被贴上部门 1 的名字纯属巧合，id = 3 的 Henry 会被贴上不存在的部门或错误部门名。
  • 加上 DISTINCT：同一部门若有两名同名同薪的不同员工（如两个 Max 都拿 $90000$），会被压成一行，正确答案应输出两行。
  • 用 HAVING salary = MAX(salary)：HAVING 作用在分组之后，salary 已不是可用的明细列，MySQL 报错或返回无意义结果。
  • 派生表忘记起别名 m：MySQL 要求每个派生表必须有别名，否则直接报「Every derived table must have its own alias」。

相似题目

题目 难度 考察点
185. 部门工资前三高的所有员工 困难 从取第一名扩展到取前三个不同薪水，DENSE_RANK() <= 3 是标准解
176. 第二高的薪水 中等 全表而非分组内取第二，且要求无解时返回 null 而非空集
178. 分数排名 中等 只求名次不做过滤，并列同名次且名次连续，正是 DENSE_RANK() 的定义
181. 超过经理收入的员工 简单 同表自连接比较两行，连接依据是指向本表的外键而非聚合结果
175. 组合两个表 简单 考左连接保留无匹配行，与本题内连接丢弃空部门形成对照
182. 查找重复的电子邮箱 简单 分组后用 HAVING COUNT(*) > 1 过滤，只需组级信息，无需连回明细
180. 连续出现的数字 中等 需要跨行比较，靠主键错位自连接而非聚合加连接
183. 从不订购的客户 简单 反向筛选无匹配行，用 NOT IN 或左连接判 null，考连接的补集语义