题目重点：按 New Grad 题目的 advance/get_room O(1)、leaderboard O(N+k) 约束设计非空房间桶和到达顺序链表，并做随机状态机对照。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 玩家在初始化时加入且 ID 唯一，均在房间 0；初始化列表顺序作为房间 0 的到达顺序。
- 房间编号 0…R，已到 R 再 advance 是 no-op，不改变到达顺序；未知玩家抛异常。题目没有规定这个边界，属于训练约定。
- 同房 tie-break 比的是最近一次进入当前房间的调用顺序，而不是玩家最初创建时间。
解题路线
- 按房间建立玩家双向链表，入房时追加尾部，保证同房早到者在前；玩家 ID 直达其节点，O(1) 摘除和查询。每桶维护人数，支持另一题目的 O(1) count_in_room。
- 另维护只含非空房间的降序双向链表与 room→bucket 索引。玩家只能 r→r+1，新房间若原本为空，它必定位于房间 r 的桶之前，故 O(1) 插入；旧桶空时 O(1) 删除。
- leaderboard 从最高房间开始，按每房到达顺序取前 k 位；无需遍历全部 R 个可能为空的房间。
- 用朴素模型在每步按 (-room,arrivalTick) 排序做独立随机对照，覆盖同房交换、空桶删除、房间人数和终点 no-op。
手动走一遍
A、B、C 初始在 0；advance(A)、advance(B)、advance(A) 后 A 在 2、B 在 1、C 在 0，前二为 A、B。若 A、B 都只前进一步，A 先进入 1，榜单中 A 排 B 前。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""O(1) advance/get and O(k) leaderboard with ordered occupied rooms."""
class PlayerNode:
def __init__(self, player_id, bucket):
self.player_id = player_id
self.bucket = bucket
self.prev = self.next = None
class RoomBucket:
def __init__(self, room):
self.room = room
self.prev = self.next = None
self.head = PlayerNode(None, self)
self.tail = PlayerNode(None, self)
self.head.next = self.tail
self.tail.prev = self.head
self.count = 0
def append(self, player):
last = self.tail.prev
last.next = player
player.prev, player.next = last, self.tail
self.tail.prev = player
player.bucket = self
self.count += 1
def empty(self):
return self.count == 0
class EscapeRoomLeaderboard:
def __init__(self, players, last_room: int):
if last_room < 0 or len(set(players)) != len(players):
raise ValueError("invalid rooms or duplicate player")
self.last_room = last_room
self.first = RoomBucket(None)
self.last = RoomBucket(None)
self.first.next = self.last
self.last.prev = self.first
self.by_room = {}
self.by_player = {}
if players:
bucket = RoomBucket(0)
self._insert_before(self.last, bucket)
self.by_room[0] = bucket
for player_id in players:
node = PlayerNode(player_id, bucket)
bucket.append(node)
self.by_player[player_id] = node
def _insert_before(self, next_bucket, bucket):
previous = next_bucket.prev
previous.next = bucket
bucket.prev, bucket.next = previous, next_bucket
next_bucket.prev = bucket
def _remove_bucket(self, bucket):
bucket.prev.next = bucket.next
bucket.next.prev = bucket.prev
del self.by_room[bucket.room]
def advance(self, player_id):
player = self.by_player[player_id]
old = player.bucket
if old.room == self.last_room:
return old.room
next_room = old.room + 1
next_bucket = self.by_room.get(next_room)
if next_bucket is None:
next_bucket = RoomBucket(next_room)
self._insert_before(old, next_bucket)
self.by_room[next_room] = next_bucket
player.prev.next = player.next
player.next.prev = player.prev
old.count -= 1
next_bucket.append(player)
if old.empty():
self._remove_bucket(old)
return next_room
def get_room(self, player_id):
return self.by_player[player_id].bucket.room
def count_in_room(self, room: int) -> int:
bucket = self.by_room.get(room)
return 0 if bucket is None else bucket.count
def leaderboard(self, k: int):
if k < 0:
raise ValueError("k must be nonnegative")
result = []
bucket = self.first.next
while bucket is not self.last and len(result) < k:
player = bucket.head.next
while player is not bucket.tail and len(result) < k:
result.append(player.player_id)
player = player.next
bucket = bucket.next
return result
复杂度
初始化 O(N)；advance/get_room O(1)；leaderboard(k) O(min(k,N))，满足题目 O(N+k) 上界；玩家节点和最多 min(N,R+1) 个非空房间桶共 O(N) 空间。
易错点与追问
容易失分的边界
- 每次 leaderboard 都扫描 0…R，R 可能远大于玩家数，无法从题给约束直接推出 O(N+k)。
- 只用 room→set，丢失同房到达顺序。
- 从旧房间列表按值删除玩家，advance 退化 O(该房间人数)。
- 玩家从 r 到 r+1 时把新桶插错位置，破坏降序。
继续深挖
- 若可跳跃任意多个房间，如何保持桶有序且仍满足更新 O(1)？
- 若允许玩家后退，同房 tie-break 如何定义？
- 并发 advance 同一个玩家时，位置和进入时间如何原子更新？
