储物柜分配与归还：最小空闲编号和最后一次分配

题目重点：最后分配编号是历史状态，归还不会把它改成当前最大柜号。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

固定柜数编号0..count−1，一用户最多占一柜；训练采用最小空闲编号优先。
无空闲返回None，重复存/未知取拒绝；last初始None，仅成功store更新。真实柜尺寸、凭证与并发另定。

解题路线

空闲编号最小堆，users映射user→locker。store弹堆、绑定、更新last；retrieve删绑定并把该柜压回堆。
核心不变量：每个柜恰处于free或某一用户绑定，二者不相交。失败store不能更新last；retrieve不能因为拿回最新柜就抹掉last。
生产可用数据库唯一(userID)、唯一(lockerID)与事务，或单分区串行化。堆加hash的Python样例不表示跨进程原子，开门动作需要命令幂等及设备确认。

手动走一遍

先分0给A、1给B，A归还，再给C分0，last=0而不是最大编号1。全满后store失败，last仍为上次成功分配；取走该柜last也保留历史编号。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heapify,heappop,heappush
class Lockers:
    def __init__(self,count):
        if count<0:raise ValueError("negative count")
        self.free=list(range(count));heapify(self.free);self.users={};self.last=None
    def store(self,user):
        if user in self.users:raise ValueError("already stored")
        if not self.free:return None
        locker=heappop(self.free);self.users[user]=locker;self.last=locker;return locker
    def retrieve(self,user):
        if user not in self.users:raise ValueError("no locker")
        locker=self.users.pop(user);heappush(self.free,locker);return locker
    def last_allocated(self):return self.last

复杂度

初始化O(K)，store/retrieve O(logK)，last O(1)，空间O(K)。

易错点与追问

容易失分的边界

归还多次会把同柜重复放堆，后续重复分配。
用户多柜合同需反向索引集合，不能直接覆盖旧绑定。

继续深挖

柜门打开成功但服务崩溃时如何恢复占用状态？
支持多尺寸时优先最小编号还是最小可容纳尺寸？