LeetCode 1204. 最后一个能进入巴士的人

2022-12-01 HGNULB 约 6 分钟

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

分类

题目描述

✅ 1204. 最后一个能进入巴士的人

题意分析

Queue 表记录了排队上车的人：person_id、person_name、weight（体重）、turn（第几个上车，从 1 开始且互不相同）。巴士的载重上限是 1000。乘客按 turn 从小到大依次上车，只要加上这个人之后总重超过 1000 就不再让他上，返回最后一个成功上车的人的 person_name。

有两处必须读准。第一，上车顺序完全由 turn 决定，不能重排也不能跳过——不存在「这个人太重就先让后面的轻的人上」这种优化，一旦某人上不去，流程就到此为止。第二，判定用的是前缀和：第 k 个人能上车，当且仅当前 k 个人的体重之和不超过 1000。

把这两点合起来看，就得到一个很有用的性质：「前 k 个人的体重和」随 k 单调递增（体重都是正数）。所以「能上车的人」一定是队伍最前面的一段连续前缀，而答案就是这段前缀的最后一个人。也正因为单调，「第一个超重的人之前的所有人都能上车」这件事自动成立，不需要额外验证。

于是问题被翻译成：求出每个人的「体重前缀和」，筛出前缀和不超过 1000 的行，取其中 turn 最大的那一行的姓名。

输出要求只有一列 person_name，且题目保证结果非空（第一个人一定上得去）。

边界：可能所有人都能上车，此时答案是 turn 最大的那个人；turn 唯一保证了不会出现并列，无需处理平局。

解法：SQL 查询建模

核心思路

题目本质是求按 turn 排序后的体重前缀和。MySQL 8 的窗口函数可以在保留每位乘客这一行的同时计算运行总和，比范围自连接更直接，也避免产生 $O(n^2)$ 个中间配对。

SUM(weight) OVER (ORDER BY turn ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) 的状态定义是：当前行的 total_weight 等于从队首到当前乘客（包含当前乘客）的体重和。显式写 ROWS 窗口框架，准确表达「从第一行累计到当前行」；turn 唯一，因此每位乘客只对应一个确定的前缀。

体重均为正数，所以前缀和随 turn 严格递增。于是 total_weight <= 1000 的行必然构成连续前缀，答案就是其中 turn 最大的一行。窗口函数产生的别名不能在同一层的 WHERE 中使用，因此先放进派生表，再在外层过滤。

正确性来自两个事实：窗口值准确表示「算上当前乘客后的总重」；可行状态具有前缀性。外层筛选保留且只保留所有能上车的人，按 turn 降序取第一行，必然就是最后一位能上车的人。

解题步骤

内层按 turn 升序计算窗口和，窗口范围从第一行到当前行，得到每位乘客上车后的 total_weight。

外层用 WHERE total_weight <= 1000 保留能上车的乘客。必须包含等号：总重恰好为 1000 仍然允许上车。

对合格行按 turn DESC 排序并 LIMIT 1，取队伍中最后的合格者；最终只选择 person_name。

以下面这份 Queue 走一遍（答案 John Cena）：

(5, 'Alice', 250, 1)、(4, 'Bob', 175, 5)、(3, 'Alex', 350, 2)、(6, 'John Cena', 400, 3)、(1, 'Winston', 500, 6)、(2, 'Marie', 200, 4)。

按 turn 排好是：1 Alice(250)、2 Alex(350)、3 John Cena(400)、4 Marie(200)、5 Bob(175)、6 Winston(500)。

窗口函数按 turn 计算出每个人上车后的前缀和：

turn = 1（Alice）：窗口只包含自己，和为 250。
turn = 2（Alex）：窗口包含 turn 1、2，和为 250 + 350 = 600。
turn = 3（John Cena）：窗口包含 turn 1、2、3，和为 600 + 400 = 1000。
turn = 4（Marie）：再加 200，和为 1200。
turn = 5（Bob）：1200 + 175 = 1375。
turn = 6（Winston）：1375 + 500 = 1875。

外层过滤保留前三行（250、600、1000）。注意 turn = 3 的和恰好等于 1000——题面说的是「不超过」，所以必须用 <=，否则 John Cena 会被误判为上不去，答案变成 Alex。

ORDER BY turn DESC 让 turn = 3 排在最前，LIMIT 1 取出 John Cena。

不需要在 SQL 中模拟「超重后停止」：正体重保证后续前缀和只会更大。若窗口错误地截止到前一行，Marie 对应的值会是 1000（漏算自己的 200），她会被误判为能上车；这说明窗口必须包含当前行。

代码实现

SELECT person_name
FROM (
    SELECT
        person_name,
        turn,
        SUM(weight) OVER (
            ORDER BY turn
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) AS total_weight
    FROM Queue
) AS q
WHERE total_weight <= 1000
ORDER BY turn DESC
LIMIT 1;

复杂度分析

时间复杂度：通常为 $O(n \log n)$，主要开销是按 turn 排序；窗口累计与外层过滤各为 $O(n)$。若执行计划能直接利用 turn 的有序访问，排序成本可以下降。

空间复杂度：最坏 $O(n)$，用于排序及窗口执行缓冲；具体占用由数据库执行计划决定。

关键点总结

「按顺序累计到当前行」对应窗口函数 SUM(...) OVER (ORDER BY ...)；显式 ROWS ... CURRENT ROW 能把边界写清楚。

窗口结果属于当前查询层的计算结果，要在外层派生表中按别名过滤。

正体重让前缀和单调递增，因此「筛出不超过 1000 的行，再取最大 turn」与逐人上车完全等价。

两个边界都要含当前值：窗口包含当前行，载重判断使用 <= 1000。

易错点总结

错误写法：窗口范围不包含当前行。上文 Marie 的累计值会被算成 1000 而非 1200，答案错误地变成 Marie。

错误写法：条件写成 total_weight < 1000。John Cena 上车后恰好 1000，正确答案会被错改成 Alex。

错误写法：在计算窗口函数的同一查询层写 WHERE total_weight <= 1000。MySQL 在 WHERE 阶段还没有生成窗口值或其别名，必须套一层派生表。

错误写法：窗口里省略 ORDER BY turn。此时得到的是全表总和，不是随上车顺序变化的前缀和。

错误写法：ORDER BY turn ASC LIMIT 1。上文会返回最先上车的 Alice，而不是最后成功上车的 John Cena。

错误写法：漏掉 ORDER BY 直接 LIMIT 1。用例任意数据：结果集顺序由执行计划决定，可能返回任意一个合格者，通过与否全靠运气。

错误写法：用普通 SUM(weight) 配合 GROUP BY 代替窗口函数。普通聚合会折叠行且没有「从队首到当前行」的窗口边界，得到的不是每位乘客的前缀和。

相似题目

题目	难度	考察点
180. 连续出现的数字	中等	同样用自连接表达行间的先后关系，条件是连续三个 `id` 值相同
181. 超过经理收入的员工	简单	自连接的入门形态，连接条件是等值而非范围
178. 分数排名	中等	「统计不小于当前值的个数」同属范围自连接，也可用窗口函数改写
1126. 查询活跃业务	中等	先聚合出分组级门槛再回筛明细，与本题「先算前缀和再筛选」骨架相同
176. 第二高的薪水	中等	同样以 `ORDER BY ... LIMIT` 取特定名次，重点在空结果的处理
185. 部门工资前三高的所有员工	困难	分组内取前 N，是自连接计数与窗口函数两种手法的综合练习