LeetCode 1204. 最后一个能进入巴士的人
题目描述
题意分析
Queue表中每行是一名候车乘客，turn决定上车先后，weight是体重。巴士总载重不得超过一千千克，需要返回最后一位能够按队列顺序上车的乘客姓名。不能跳过队伍中间的人去选择更轻的乘客，也不是寻找单人体重最大的人。判断某人能否上车，必须计算从队首到他这一整段的累计体重；刚好达到一千仍然允许。题目保证第一位乘客能够上车。
解法：SQL 查询建模
核心思路
[!blue]
按
turn排序后，每个人对应一个“包含当前乘客的队伍前缀”。把这个前缀的体重求和，就得到了他上车之后的总重。随着后续乘客加入，总重不会下降，所以可以上车的人恰好组成队伍的一段前缀。使用
SUM(weight) OVER (...)计算累计体重。窗口函数为每位乘客保留原来的一行，并附加这个前缀总和；它不会像直接聚合那样把整队乘客压成一个总数。窗口内按turn排序，范围明确写成从第一行到当前行，确保当前乘客的体重也包含在判断中。把窗口结果作为派生表
q，外层再用total_weight <= 1000筛选。这样筛选发生在累计值生成之后；不能在同一层的WHERE中直接使用尚未计算的窗口结果，也不能先过滤单人体重再对剩下的人累加，那会改变实际排队前缀。筛选后留下的都是能上车的乘客，再按
turn降序取第一行，就是合法前缀中顺位最后的一位。内层升序负责累计，外层降序负责选出末尾，两种排序的目的不同。最终只输出要求的person_name。
解题步骤
- 内层保留姓名和顺位，并计算
SUM(weight) OVER (ORDER BY turn ...)。- 将窗口范围设为
ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW，累加队首到当前人的体重。- 外层筛选累计值不超过一千的行。
- 按
turn DESC排序并使用LIMIT 1，返回最后一位合法乘客的姓名。
代码实现
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+1))$，窗口累计与筛选是线性处理；实际是否利用顺位索引、如何执行外层取首行，由数据库执行计划决定。
- 空间复杂度：排序、派生表和窗口缓冲在常见实现中最坏为 $O(n)$，具体取决于执行计划及是否物化。
关键点总结
[!green]
- 窗口函数保留每个乘客，同时计算包含他本人的累计体重。
- 先生成累计值，再筛选合法前缀，最后按顺位选择末尾。
- 顺位列而非人员编号或姓名决定上车顺序。
易错点总结
[!yellow]
- 窗口不包含当前行，会用上车之前的总重判断当前人，错误接纳超重者。
- 条件写成严格小于一千，会排除刚好满载的合法乘客。
- 按单人体重筛选或先跳过某些乘客，会改变题目要求的连续上车顺序。
- 外层升序后取第一行，得到的是最先上车的人，而不是最后一位。
- 只对整表求一个体重总和，无法保留每名乘客对应的累计位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1308. 不同性别每日分数总计 | 中等 | 同样按给定顺序计算累计总量，本题再筛出累计重量不超过容量的最后一条排队记录。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！