江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第184题：部门工资最高的员工

表: Employee +--------------+---------+ | 列名 | 类型 | +--------------+---------+ | id | int | | name | varchar | | salary | int | | departmentId | int | +--------------+---------+ id是

题目描述

表: Employee

+--------------+---------+
| 列名          | 类型     |
+--------------+---------+
| id           | int     |
| name         | varchar |
| salary       | int     |
| departmentId | int     |
+--------------+---------+
id是此表的主键列。
departmentId是Department表中ID的外键。
该表的每一行都表示员工的ID、姓名和工资。它还包含他们所在部门的ID。

表: Department

+-------------+---------+
| 列名         | 类型     |
+-------------+---------+
| id          | int     |
| name        | varchar |
+-------------+---------+
id是此表的主键列。
该表的每一行表示部门ID和部门名称。

编写SQL查询以查找每个部门中薪资最高的员工。 按 任意顺序 返回结果表。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1:

输入：
Employee 表:
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Jim   | 90000  | 1            |
| 3  | Henry | 80000  | 2            |
| 4  | Sam   | 60000  | 2            |
| 5  | Max   | 90000  | 1            |
+----+-------+--------+--------------+
Department 表:
+----+-------+
| id | name  |
+----+-------+
| 1  | IT    |
| 2  | Sales |
+----+-------+
输出：
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Jim      | 90000  |
| IT         | Max      | 90000  |
| Sales      | Henry    | 80000  |
+------------+----------+--------+
解释: Max 和 Jim 在 IT 部门的工资都是最高的，Henry 在销售部的工资最高。

提示

  • Employee 表中的 departmentId 是 Department 表中 id 的外键。
  • 一个部门可能有多个获得最高工资的员工。

解题思路

方法一：使用 JOIN 和子查询

解决这道题的关键是找出每个部门的最高工资，然后将这个结果与员工表和部门表连接，找出对应的员工信息。

关键点：

  1. 使用子查询找出每个部门的最高工资
  2. 将该子查询与员工表和部门表连接
  3. 筛选出工资等于部门最高工资的员工

时间复杂度：O(n+m)，其中 n 和 m 分别是 Employee 表和 Department 表的行数 空间复杂度：O(n)

方法二：使用 JOIN 和窗口函数

另一种解决方法是使用窗口函数，如 MAX()，对每个部门的员工按工资进行排名，然后筛选出排名第一的员工。

关键点：

  1. 使用窗口函数 MAX() OVER(PARTITION BY departmentId) 计算每个部门的最高工资
  2. 将员工表与部门表连接
  3. 筛选出工资等于部门最高工资的员工

时间复杂度：O(n log n)，其中 n 是 Employee 表中的行数（排序的时间复杂度） 空间复杂度：O(n)

方法三：使用 JOIN 和 IN

也可以使用 IN 操作符和子查询，先找出每个部门的最高工资，然后找出满足部门和工资条件的员工。

关键点：

  1. 使用子查询找出每个部门的最高工资，形成 (departmentId, maxSalary) 对
  2. 使用 IN 操作符找出满足条件的员工
  3. 将结果与部门表连接获取部门名称

时间复杂度：O(n*m)，其中 n 和 m 分别是 Employee 表和 Department 表的行数 空间复杂度：O(n)

代码实现

SQL 实现（方法一：JOIN 和子查询）

SELECT 
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
FROM 
    Employee e
JOIN 
    Department d ON e.departmentId = d.id
WHERE 
    (e.departmentId, e.salary) IN (
        SELECT 
            departmentId, MAX(salary)
        FROM 
            Employee
        GROUP BY 
            departmentId
    );

SQL 实现（方法二：JOIN 和窗口函数）

SELECT 
    Department,
    Employee,
    Salary
FROM (
    SELECT 
        d.name AS Department,
        e.name AS Employee,
        e.salary AS Salary,
        MAX(e.salary) OVER (PARTITION BY e.departmentId) AS max_salary
    FROM 
        Employee e
    JOIN 
        Department d ON e.departmentId = d.id
) t
WHERE 
    Salary = max_salary;

SQL 实现（方法三：JOIN 和 IN）

SELECT 
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
FROM 
    Employee e
JOIN 
    Department d ON e.departmentId = d.id
WHERE 
    e.salary = (
        SELECT 
            MAX(salary)
        FROM 
            Employee
        WHERE 
            departmentId = e.departmentId
    );

性能分析

各SQL实现的性能对比：

实现方法 执行用时 内存消耗 特点
方法一 590 ms 0B 使用IN和子查询，代码简洁
方法二 517 ms 0B 使用窗口函数，性能较好
方法三 646 ms 0B 使用相关子查询，直观但性能较差

补充说明

代码亮点

  1. 方法一使用 (departmentId, salary) IN (…) 形式，代码简洁
  2. 方法二使用窗口函数，避免了多次扫描表
  3. 方法三使用相关子查询，思路直观易懂

方法比较

不同方法各有优缺点：

JOIN 和子查询：

  • 代码简洁，易于理解
  • 性能通常不错，特别是当表已经建立了适当的索引
  • 支持多列比较，如 (departmentId, salary) IN (…)

窗口函数：

  • 避免了多次扫描表，性能通常更好
  • 代码结构清晰，易于扩展
  • 不是所有数据库都支持窗口函数

相关子查询：

  • 思路最直观，类似于自然语言描述
  • 在某些情况下性能可能较差，特别是对大型表
  • 对于每一行都要执行一次子查询

对于本题，窗口函数方法通常是更好的选择，因为它既清晰又高效。

常见错误

  1. 忘记处理同一部门有多个最高工资员工的情况
  2. 没有正确连接 Department 表获取部门名称
  3. 没有使用 GROUP BY 进行分组，导致结果不正确
  4. 结果列名格式不符合要求

相关题目