最后一个能进电梯的人:累计和不超过上限
LeetCode 1204 · 累计求和、取满足条件的最后一行
面试怎么回答
用 SUM(weight) OVER (ORDER BY turn) 得到按顺序的累计体重,筛选累计值 <= 1000 的行,按 turn 降序取第一个人。累计求和 + 过滤 + 取边界,是处理「额度用到哪里为止」这类问题的通用写法。
先把这段讲顺;面试官追问时,再展开下面的原理和细节。
详细讲解
题意
排队表记录每个人的体重和排队顺序。电梯载重上限 1000,大家按顺序进电梯,找出最后一个进去后总重量不超过上限的人。
表结构
- Queue:person_id(主键)、person_name、weight、turn(1 到 n)
思路
按排队顺序算累计体重,累计值不超过 1000 的人都能进;其中顺序最靠后的那个就是答案。用 SUM OVER (ORDER BY turn) 得到累计值,过滤后按累计值或 turn 降序取第一。
参考解法
select person_name
from(
select person_name ,sum(weight) over(order by turn) t
from Queue
)t1
where t<=1000
order by t desc
limit 1
易错点
- 按 turn 排序算累计,不能按 person_id。
- 默认窗口在 ORDER BY 值重复时会把同值行一起累计;这里 turn 唯一,不受影响。