LeetCode 181. 超过经理收入的员工

2022-02-11 HGNULB 约 7 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 181. 超过经理收入的员工

题意分析

Employee 表里每行是一名员工，含 id、name、salary 与 managerId。managerId 指向同一张表里另一行的 id，表示这名员工的直属经理；没有经理的人（比如老板）该字段为 NULL。要找出所有薪水严格高于自己直属经理的员工，输出他们的姓名，列名固定为 Employee。

这道题的结构特点是层级关系被压在同一张表里：员工和经理是同类实体，靠一个自引用外键连接。要比较「员工的薪水」与「经理的薪水」，必须让同一张表的两行同时出现在一个比较表达式中——这正是自连接的用武之地。

「严格高于」意味着薪水相等的不算。这是一个容易被 >= 误伤的边界。

managerId 为 NULL 的行必须被排除。它们本身没有经理，「超过经理收入」这个命题对它们无意义。好在 NULL 参与等值连接时永远不成立，内连接会自动把它们过滤掉，不需要额外写 WHERE managerId IS NOT NULL。

输出只要姓名一列，且列名必须是 Employee——注意这与表名同名，但语义完全不同，别名不能省。

边界包括：表中只有老板一人；某个 managerId 指向的行不存在（脏数据，内连接同样会过滤掉）；以及员工与经理薪水完全相等。

解法：SQL 查询建模

核心思路

直觉写法是用标量子查询：对每一行去查它经理的薪水，再比较。这在语义上没问题，但它是关联子查询——外层每扫一行，内层就要执行一次查找，在没有索引的情况下退化成 $O(n^2)$，而且优化器对这类写法的重写能力有限。

瓶颈在于「取经理的薪水」被当成了逐行的即席查询，而它本质上是一次表与表之间的匹配。一旦把它表述成连接，优化器就能选择哈希连接或索引嵌套循环，成本大幅下降。

关键观察是：员工和经理虽然来自同一张物理表，但在这次查询里扮演的是两个不同的角色。SQL 通过给同一张表起两个不同的别名来表达这件事——e1 代表「员工」这个角色，e2 代表「经理」这个角色。有了两个别名，同一张表就像两张表一样参与连接，e1.salary 与 e2.salary 也就能出现在同一个比较里了。

连接条件是 e1.managerId = e2.id：把员工行与它经理所在的那一行配对。这个方向不能反——e1.id = e2.managerId 表达的是「e2 是 e1 的下属」，角色互换后筛选条件的含义也跟着反了。

筛选条件是 e1.salary > e2.salary，直接翻译「员工薪水高于经理」。

用 JOIN（内连接）而不是 LEFT JOIN，是因为没有经理的员工本就不该出现在结果里。内连接在 managerId 为 NULL 时因等值比较不成立而自动丢弃这些行，恰好符合需求；用左连接则会把它们保留下来，虽然随后会被 WHERE 中的比较过滤掉（NULL > NULL 结果为未知），但语义表达不如内连接直白。

解题步骤

确定输出粒度是「每名符合条件的员工一行」，所以主表是员工角色的那份 Employee，别名取 e1。粒度定了，才知道该从哪张表出发。

把同一张 Employee 以别名 e2 再引入一次，代表经理角色。两个别名必不可少：没有别名，salary 这个列名会有歧义，数据库直接报错。

连接条件写 ON e1.managerId = e2.id。含义是「e2 这一行正是 e1 的经理」。写成 e1.id = e2.managerId 会把角色对调，筛选出的将是「经理薪水高于下属」的那批人，结果完全不同。

筛选条件写 WHERE e1.salary > e2.salary。用严格大于，因为题目要求「超过」而非「不低于」。

选出 e1.name 并起别名 Employee。要选员工角色的姓名而不是经理的；别名是题目规定的输出列名，不能省也不能改大小写。

以一张具体的表走一遍：Employee 中有 (1, 'Joe', 70000, 3)、(2, 'Henry', 80000, 4)、(3, 'Sam', 60000, NULL)、(4, 'Max', 90000, NULL)。

连接阶段逐行匹配。e1 取 Joe 时 managerId = 3，在 e2 中找到 id = 3 的 Sam，配对成功，得到一行 (Joe, 70000, Sam, 60000)。e1 取 Henry 时 managerId = 4，匹配到 Max，得到 (Henry, 80000, Max, 90000)。e1 取 Sam 时 managerId 为 NULL，与任何 e2.id 的等值比较结果都是未知，无法配对，该行被内连接丢弃。e1 取 Max 时同理被丢弃。

筛选阶段。第一行 $70000 > 60000$ 成立，保留；第二行 $80000 > 90000$ 不成立，剔除。

最终输出一行：Joe，与预期一致。

若把连接条件写反成 e1.id = e2.managerId，e1 取 Sam 时会匹配到下属 Joe，比较 $60000 > 70000$ 不成立；e1 取 Max 时匹配到 Henry，比较 $90000 > 80000$ 成立，于是输出 Max——找出来的是「薪水高于下属的经理」，与题意南辕北辙。

代码实现

-- 同一张表起两个别名，分别扮演「员工」与「经理」两个角色。
SELECT e1.name AS Employee
FROM Employee e1
JOIN Employee e2
    ON e1.managerId = e2.id
WHERE e1.salary > e2.salary;

复杂度分析

时间复杂度：取决于执行计划。题目中的 id 是主键时，通常扫描员工行并按主键索引查经理，量级可记为 $O(n \log n)$；支持哈希连接的数据库也可能选择 $O(n)$ 的建表与探测。若连接列没有索引且执行器采用朴素嵌套循环，最坏会退化为 $O(n^2)$，不能笼统断言“无索引一定是哈希连接”。

空间复杂度：哈希连接需要 $O(n)$ 的哈希表；索引嵌套循环只需常数级额外工作内存。具体取决于执行计划，输出行数不超过 $n$。

关键点总结

表内存在自引用外键（本行的某列指向同表另一行的主键）时，把它拆成两个别名做自连接，是表达层级关系的标准手法。上下级、父子分类、前后订单都适用同一套模式。

别名承担的是「角色」语义。写连接前先想清楚每个别名代表谁，连接条件与筛选条件都要围绕这个角色分配来写，否则会写出方向相反却语法正确的查询——这类错误最难发现，因为它照样能跑出结果。

连接条件的方向由外键指向决定：外键在哪一侧，就写在等号的哪一侧。e1.managerId = e2.id 读作「e1 的经理是 e2」，读得通方向就对。

内连接天然过滤掉外键为 NULL 的行，这是「无匹配即排除」需求的免费实现，比显式写 IS NOT NULL 更简洁。反过来，需要保留无匹配行时才用左连接。

输出列名由题目规定，必须用 AS 显式指定，不能依赖数据库对列名的默认推断。

易错点总结

错误写法：连接条件写成 ON e1.id = e2.managerId。用例：(1,'Joe',70000,3)、(3,'Sam',60000,NULL) → 角色对调后比较的是经理 Sam 是否比下属 Joe 薪水高，查询返回空集；正确连接应输出员工 Joe。

错误写法：筛选条件用 >=。用例：(1,'A',50000,2)、(2,'B',50000,NULL) → A 与经理薪水相等也被选出，正确答案是空结果。

错误写法：选出 e2.name。用例：(1,'Joe',70000,3)、(3,'Sam',60000,NULL) → 输出经理 Sam，正确答案是员工 Joe。

错误写法：不起别名，直接写 FROM Employee JOIN Employee ON ...。用例：任意数据 → 数据库无法区分两份表的同名列，报「Not unique table/alias」错误，查询无法执行。

错误写法：输出列不加 AS Employee。用例：任意数据 → 列名被推断为 name，与题目要求的 Employee 不符，判定失败。

错误写法：用 LEFT JOIN 并把筛选条件写进 ON 子句。用例：(3,'Sam',60000,NULL) → 条件放进 ON 后左连接会保留所有 e1 行，Sam 这类没有经理的人也被输出（其经理列为 NULL），正确答案不应包含他们。

错误写法：用逗号连接却漏写连接条件，如 FROM Employee e1, Employee e2 WHERE e1.salary > e2.salary。用例：四行数据 → 产生笛卡尔积，每个员工与所有薪水更低的人配对，输出大量重复且错误的姓名。

错误写法：额外加上 WHERE e1.managerId IS NOT NULL 却用了 LEFT JOIN 并把比较写成 e1.salary > e2.salary。用例：某员工的 managerId 指向一个不存在的 id → 左连接保留该行且 e2.salary 为 NULL，70000 > NULL 求值为未知、该行被过滤，结果虽对但逻辑绕；内连接一步到位。

错误写法：用 DISTINCT 去重姓名。用例：两名同名员工都符合条件 → 结果被压成一行，正确答案应输出两行，因为判定的是员工记录而非姓名取值。

错误写法：把比较写成 e1.salary - e2.salary > 0 但列类型允许 NULL。用例：某行 salary 为 NULL → 减法结果为 NULL，比较求值为未知，该行被静默丢弃；虽然本题 salary 非空，但这种写法在字段可空时会掩盖问题。

相似题目

题目	难度	考察点
182. 查找重复的电子邮箱	简单	同样在一张表内找关系，但用 `GROUP BY` 加 `HAVING` 而非自连接更简洁
196. 删除重复的电子邮箱	简单	自连接从查询变成删除，连接条件里的比较用于挑出「该删的那一份」
184. 部门工资最高的员工	中等	连接的是两张不同的表，还要在分组内取最大值，比自连接多一层聚合
176. 第二高的薪水	中等	无连接，考点是排序定位与空结果时返回 `NULL`
178. 分数排名	中等	用窗口函数为每行附加统计量，展示「保留明细并加一列」的另一条路径
185. 部门工资前三高的所有员工	困难	连接与分组内排名叠加，是本题与 178 两种技巧的组合
1280. 学生们参加各科测试的次数	简单	交叉连接补全所有组合后再左连接计数，重点是「无匹配也要保留」的场景
1204. 最后一个能进入巴士的人	中等	自连接用于累加前缀重量，展示同一技巧如何表达「本行与之前所有行」的关系