LeetCode 1396 Design Underground System这道“设计地铁系统”的题目我至少刷过三遍。第一遍用最朴素的思路交了学费第二遍才真正看懂题目的精妙之处。如果你正在准备面试或者刷题刷到了 LeetCode 热门题单里这一道我强烈建议你把它当成“哈希表 增量统计”的范本来研究——它不像很多模拟题那样只需要照着流程写 if-else它对数据结构的选择有明确的性能要求题目描述里还埋着几个容易被忽略的约束条件。题目要求实现一个UndergroundSystem类提供checkIn、checkOut、getAverageTime三个方法乘客刷卡进站时记录起点站和时间刷卡出站时记录终点站和时间系统随时回答“从 A 站到 B 站平均要多久”。它适合三类人阅读想弄懂 LeetCode 设计题的刷题者、面试前想快速复习哈希表应用的求职者、以及想用一个经典小案例理解“流式聚合”思维的工程师。下面我直接从自己的刷题复盘讲起把这道题从思路、实现到踩坑一次性拆透。1. 为什么一上来就写“模拟版本”的人多半要翻车1.1 大多数人脑海中的第一版答案我最初看到这道题的瞬间第一反应是这有什么难的维护一个列表把每一条已经完成的行程存下来不就行了。checkOut的时候追加一条(id, 起点站, 终点站, 耗时)的记录getAverageTime的时候从列表里筛出所有起点和终点匹配的记录求和除以条数。代码五分钟就能写完示例用例也能通过。当时的代码大致长这样错误示范class UndergroundSystem: def __init__(self): self.records [] # 每完成一段行程就往里面塞一条 def checkIn(self, id, stationName, t): self.check_in[id] (stationName, t) def checkOut(self, id, stationName, t): start, start_t self.check_in[id] self.records.append((start, stationName, t - start_t)) def getAverageTime(self, startStation, endStation): total 0 cnt 0 for start, end, cost in self.records: if start startStation and end endStation: total cost cnt 1 return total / cnt逻辑上没有任何错误。但它有一个致命的代价getAverageTime的耗时是 O(N)N 是累计完成的行程数。这个隐患在题目给出的示例数据里根本看不出来。1.2 题目数据规模下的真实代价LeetCode 给的方法调用总次数上限大约是 2 × 10^4。听起来不是很大但极端情况下可以构造出非常难受的序列先执行接近两万次checkIn checkOut产生近万条行程记录然后连续调用一万次getAverageTime查询同一个路线。每一次查询都遍历一遍这近万条记录总操作量就是 10^4 × 10^4 10^8 量级。10^8 次基础操作在 Python 的循环里是什么概念本地跑一次都会肉眼可见地卡顿LeetCode 的评测环境自然会给 TLE。我当时提交的直接结果就是超时。我盯着屏幕愣了一下然后才意识到这道题根本不是让你去“模拟”一个地铁系统而是让你用聚合统计去顶住高频查询。真正让问题变严重的是getAverageTime的调用次数完全不受行程数量的限制。你可以只有一条行程却查一万次也可以有九千条行程一次都不查。把查询做成 O(N)就是让系统的吞吐量被历史数据总量绑架。1.3 从“存明细”到“算汇总”的关键认知转折被 TLE 教育过一次之后我开始重新审视题目。需求的核心是“从 A 站到 B 站的平均耗时”。平均值的数学结构其实非常简单平均耗时 总耗时 / 完成行程次数这意味着我真正需要维护的只有两个数字而不是一大把明细记录。每当一次checkOut完成我可以立刻把这段行程的耗时加到“总耗时”里同时把“次数”加一。查询的时候只需要做一次除法。这就是“增量聚合”的核心思想在数据产生的时刻把答案算好一部分而不是等到被问的时候再去现算。把这条认知理顺之后代码结构整个就变了。上面那段又慢又占内存的代码可以被两张哈希表彻底替代。2. 核心设计在线乘客表 路线统计表的分工逻辑2.1 第一张表记录“在途乘客”的临时状态第一张哈希表负责处理所有还没出站的乘客。它以乘客 id 为键以(进站站名, 进站时间)为值。为什么需要它因为一次完整的行程由两个事件组成进站事件和出站事件。这两个事件是分散到达的之间隔着一段不确定的时间。举个例子乘客 5 在某站刷卡进站系统只知道“5 号乘客现在在车上起点是 A进站时间是 10:00”。如果此时系统不把这条信息记下来等到乘客 5 在 C 站刷卡出站时系统就完全不知道他到底从哪来的、已经坐了多久。所以这张表本质上是一个“会话状态表”专门等待后续的出站事件来配对结算。这张表的生命周期是短暂的。乘客一旦出站这条记录就完成了使命应该立刻删除。如果一直保留不仅浪费内存还会在极端情况下积累出大量过期数据。2.2 第二张表路线维度的累计账本第二张哈希表负责记录所有已完成行程的统计信息。它以(起点站, 终点站)为键以[总耗时, 完成次数]为值。每当一次checkOut发生系统拿到起点、终点、本次耗时做一次累加即可。这里有一个非常重要的设计决策统计的 key 里绝不能带乘客 id也不该保存每一次行程的明细。因为查询口径是“所有从 A 到 B 的乘客平均耗时”它是一个路线维度的聚合值。同一个乘客假如今天从 A 到 B 走了三次这三次应该作为三个样本进入统计而不是被合并成一条。把乘客维度从统计表里拿掉才能保证所有完成行程都按路线正确归并。第二张表一旦建立getAverageTime就退化成了“查表 除法”。无论系统里已经累积了几千条还是几百万条行程只要这张表存在查询都是 O(1)。2.3 用一句话向面试官讲清楚整个设计这道题面试频率不低。我后来在模拟面试里被问到习惯用一句话先立框架“我用第一张哈希表保存未完成行程的上下文用第二张哈希表保存已完成行程的聚合结果所有方法都是 O(1)。”然后马上拆开讲细节。这个设计并不难但它非常优雅地模拟了一种真实系统里的常见架构把“进行中的事务”和“已完成事务的汇总”分开管理。如果从流式处理的角度看第一张表是“窗口状态”第二张表是“聚合输出”。每次checkIn是在往窗口里写状态每次checkOut是在做“双流关联 聚合”。打个比方check_in表像餐厅门口的就座登记簿客人进门先记一桌结账时翻到这一桌算消费金额算完就划掉路线统计表像收银台的每日流水汇总每个菜品的销量和营业额一直累加而不是把每张订单都贴在墙上。客人随时来问“今天 A 套餐平均卖多少钱”收银台直接给一个数不需要把一千张订单重新翻一遍。3. 参考实现拆解Python 为主C 要点对比3.1 完整可运行的 Python 代码下面是我最终采用的 Python 实现非常短核心就三个方法from collections import defaultdict class UndergroundSystem: def __init__(self): # 在途乘客id - (起点站, 进站时间) self.check_in {} # 路线汇总(起点站, 终点站) - [总耗时, 已结算次数] self.travel_stats defaultdict(lambda: [0, 0]) def checkIn(self, id: int, stationName: str, t: int) - None: self.check_in[id] (stationName, t) def checkOut(self, id: int, stationName: str, t: int) - None: start_station, start_time self.check_in.pop(id) stats self.travel_stats[(start_station, stationName)] stats[0] t - start_time stats[1] 1 def getAverageTime(self, startStation: str, endStation: str) - float: total, count self.travel_stats[(startStation, endStation)] return total / count这段代码能直接通过 LeetCode 的判定。下面我逐行拆开讲为什么这么写。3.2 逐方法解读每个选择背后的理由__init__里初始化两个容器。check_in用普通字典因为每个乘客只会有一条在途记录使用defaultdict反而没有意义。travel_stats用defaultdict(lambda: [0, 0])这样第一次访问某个路线的时候会自动生成一个可写的[0, 0]列表省掉了一行if key not in dict的判断。checkIn方法只有一行赋值。题目保证同一个乘客在未出站前不会再次调用checkIn所以直接覆盖写入是安全的。如果你要面对的是可能重复进站的脏数据那就要加一个防御性判断但 LeetCode 的约束下不需要。checkOut是核心。这里用了pop而不是先get再del。pop会同时完成两件事取出在途记录并把它从字典里删除。有些人在这一步只get不删除虽然不影响结果但会导致check_in表不断积累已完成行程的历史残留。短期没问题跑久了内存会白白膨胀面试官看到这里往往也会追问。取出起点和时间后计算本次耗时t - start_time然后累加到对应路线的统计。注意这里travel_stats的 key 是(start_station, stationName)这个元组而不是拼接字符串。为什么用元组我后面专门讲。getAverageTime直接查表做除法。Python 的/返回浮点数天然符合题目要求的float返回类型。3.3 用一个实际用例逐步演示内部状态变化为了确认实现没有问题我建议你亲手模拟一遍下面这段调用。这里特意让同一个乘客 1 号两次走同一条路线验证聚合逻辑对重复行程的处理us UndergroundSystem() us.checkIn(1, A, 10) us.checkOut(1, C, 20) # 完成 A-C耗时 10 us.checkIn(1, A, 30) us.checkOut(1, C, 42) # 完成 A-C耗时 12 print(us.getAverageTime(A, C)) # 预期 (1012)/2 11.0每次操作后两个哈希表的内容如下操作check_in表travel_stats表checkIn(1, A, 10){1: (A, 10)}{}checkOut(1, C, 20){}{(A,C): [10, 1]}checkIn(1, A, 30){1: (A, 30)}{(A,C): [10, 1]}checkOut(1, C, 42){}{(A,C): [22, 2]}可以看到第二次完成同样的路线后并没有新增一条记录而是在原来的[总耗时, 次数]上做了累加。最终getAverageTime(A, C)取到[22, 2]返回11.0。这个例子把“增量聚合”四个字体现得很直观系统自始至终只需要保存一个累计值和一个人数不需要知道第一次耗时 10、第二次耗时 12 这些细节。3.4 C 与 Java 实现的关键注意点C 版本的思路完全一致但有两个坑需要特别留意。第一个是累计值要用long long。题目虽然没有把时间上限写得特别吓人但方法调用上限约 2 × 10^4单次耗时又能构造到 10^6 量级累计总耗时完全可能超过 2^31 - 1。用int会在极端数据下溢出。第二个是除法强转total / count在 C 里如果两个操作数都是整型结果是整数除法需要先把分子转成double。我平时在 LeetCode 上用 C 写的话会这样写class UndergroundSystem { public: unordered_mapint, pairstring, int inTransit; unordered_mapstring, pairlong long, int stats; void checkIn(int id, string stationName, int t) { inTransit[id] {stationName, t}; } void checkOut(int id, string stationName, int t) { auto [start, startTime] inTransit[id]; inTransit.erase(id); string key start ~ stationName; stats[key].first t - startTime; stats[key].second; } double getAverageTime(string startStation, string endStation) { string key startStation ~ endStation; auto [total, cnt] stats[key]; return (double) total / cnt; } };我在这个 C 版本里用了~作为分隔符拼接 key。你在提交时这么写没问题因为 LeetCode 的测试数据里站名都是普通字符串不会包含分隔符。但在面试中我建议你主动补一句更稳妥的做法是使用结构化的复合 key比如pairstring,string并为unordered_map提供自定义哈希避免站名本身包含分隔符时出现 key 歧义。Java 版本则是一组HashMapInteger, String[]加HashMapString, long[]key 用起点和终点拼接值用long[2]分别存总耗时和次数。只要记住溢出问题实现上差别不大。4. 踩坑记录我在这道题上交过的四次学费4.1 坑一把行程明细全部存下来查询时全表扫描这个坑我在第一节已经完整描述过第一版提交直接 TLE。当时的排查过程很简单本地造了一个两万次调用的极端用例测出getAverageTime的耗时随历史记录数量线性增长立刻意识到问题出在“查询时遍历”。这里想强调一个排查思路如果一道题的多次操作复杂度出现“一次 O(N)”和“一次 O(1)”的悬殊差异并且查询会被高频调用那么预聚合几乎总是答案。不要指望测试数据温和刷题要按最坏复杂度估算。4.2 坑二统计 key 里误带了乘客 id这个错误比第一个更隐蔽因为它不会 TLE而是直接产生错误答案。我第一次重写代码时脑子里还在想着“每个人的行程是独立事件”于是把统计 key 设计成了(id, startStation, endStation)每次checkOut都在自己 id 的桶里累加。结果就是两个不同乘客走同一条路线被拆成了两个互不可见的统计桶一个乘客多次走同一条路线虽然累加到了一起但其他乘客的数据完全参与不进来。getAverageTime自然查不到全局平均值。后来我盯着错误输出想了几分钟意识到问题出在“聚合粒度”上。路线统计的粒度是车站对而不是乘客、更不是单次行程事件。所有发生在同一车站对之间的行程无论谁走的都应该进入同一个累加桶。把 id 从 key 里拿掉一切恢复正常。好的做法是check_out表把(startStation, endStation)作为唯一身份id只用于找到进站记录不参与路线统计。这个区分在面试里很加分因为它说明你想清楚了“这个系统到底按什么维度出报表”。4.3 坑三用字符串拼接路线 key被站名里的分隔符坑到我一开始在 C 版本里习惯这样写 keystring key startStation - endStation;这个写法简单、可读性好但存在一个理论上的歧义。假设存在四个站“A”、“B-C”、“A-B”、“C”。那么路线(A, B-C)和路线(A-B, C)拼出来的字符串都是A-B-C。这是两条完全不同的路线统计却会被错误地合并到一起。Python 版本的tuple天然避开了这个问题(A, B-C)和(A-B, C)是两个完全不同的哈希键。C 里如果不想自定义哈希可以约定站名不包含分隔符但我在生产环境里绝不会把宝押在“数据恰好干净”上。我当时是怎么排查到这个问题的并不是因为 LeetCode 的用例逼我踩坑而是我在本地造数据时突发奇想给车站取了个包含-的名字结果平均时间出现了明显的错误。这个经历让我养成一个习惯设计 key 时优先考虑结构化组合而不是字符串硬拼。4.4 坑四忘记 pop 导致内存膨胀C 的 int/int 除法截断这两个问题都是提交通过之后才暴露的属于“能被 AC 但经不起深挖”的代码质量隐患。第一check_out里如果只get不popcheck_in表里会积累大量已经出站的乘客记录。虽然下一次同一 id 进站时会被覆盖但那些只进站一次、再也没回来的乘客记录会永远留在内存里。数据量小看不出来一旦把方法调用次数推到上限内存占用会明显偏大。我在 LeetCode 上提交过一个“能过但内存排名很差”的版本就是因为这个。第二C 里getAverageTime如果写成return total / count;而total和count都是long long那么结果会被截断成整数。比如总耗时 11、次数 2返回值是 5.0 而不是 5.5。LeetCode 的返回类型是double不会报类型错误但答案会因为精度而错误。必须写成return (double) total / count;。这个错误在示例用例上往往看不出来因为示例数据刚好整除。另外提一句Python 的total / count是真正的浮点除法没有这个问题这也是很多 Python 党用习惯了之后写 C 会踩坑的原因。5. 面试追问与真实系统映射从地铁闸机到流式聚合5.1 如果面试官要求支持换乘路径原题模型会发生什么原题的模型里checkIn和checkOut只给出了行程的首尾两站。如果乘客中途换乘过系统是不知道的。真实的地铁票务系统需要给“从 A 到 C 的平均时间”这本身没有歧义——它只关心首尾。但如果面试官追加条件“我想知道 A 到 C 的所有行程中经由 B 换乘的平均时间”原题模型就不够用了。这时候需要把“单次进站-出站对”扩展成“多段路径事件表”。一种常见做法是把每段换乘也看成一次独立的“进出站事件”乘客从 A 进站、B 出站后再从 B 进站、C 出站系统记录的是两段子线路的耗时。要统计 A 到 C 的换乘耗时就得先把同一乘客相邻两段行程拼接起来。这个扩展本质上把问题从“两表汇总”升级成了“图分析 路径拼接”复杂度高了一个量级。我提到这一点是想说明原题之所以用两张哈希表就能搞定正是因为“首尾直达”这个简化假设。面试时主动说出这个假设能避免被追问时手忙脚乱。5.2 如果要分时段统计改动量有多大真实场景里早高峰和晚高峰的平均耗时会明显高于平峰。想让系统支持分时段统计只需要把统计表的 key 从(start, end)扩展成(start, end, 时段标签)在checkOut时根据出站时间判断该归入哪个桶。代码改动很小核心逻辑完全不变。这个追问的价值在于考察你是否清楚“聚合粒度是系统设计的关键决策”。如果你能在面试中顺着这个思路说“加一个维度只是扩大 key聚合更新和查询逻辑都不用改”面试官通常会很满意。5.3 这道题在真实世界里到底像什么有一次和朋友聊到城市地铁的自动售检票系统他说后台其实不会把每一笔刷卡明细都放在内存里算平均。乘客刷卡进站的数据会进入一张临时表刷卡出站时后台把进站记录和出站记录做一次关联算出行程时长紧接着就把聚合结果累加到站点对的统计里。这和 LeetCode 1396 的思路几乎一模一样。共享单车、停车场、网约车平台也都有同样的需求开锁/进站是checkIn关锁/出场/到达是checkOut平台要回答“从 A 区到 B 区平均骑行时长”、“某个停车场平均停车时长”等等。这些系统的数据量一天可能就是几百万条没有人会在查询时去扫描全量明细。先写审计日志再把可丢的明细归档内存里只保留聚合值这是统一的套路。5.4 与 LRU Cache、Logger Rate Limiter 等设计题横向对比刷题刷到后面会发现LeetCode 的设计题有一条非常清晰的主线选一个“当前状态”的数据结构再选一个“历史结果”的查询结构。拿几道经典题对比题目当前状态保存什么历史结果怎么查询1396 Design Underground System在途乘客的进站信息路线平均耗时直接查表146 LRU Cachekey 到值、key 到访问顺序每次 get 维护访问顺序359 Logger Rate Limiter消息到最近时间戳根据时间戳判断是否放行362 Design Hit Counter最近时间窗口的计数数组直接对窗口求和这几道题没有一道需要把“所有历史事件”都留在内存里。它们都只保留“回答当前/最近查询所需的最小状态”。如果你能从 1396 里总结出这条主线再去做其他设计题会比单纯背答案有效得多。6. 实测表现与举一反三的个人心得6.1 我在 LeetCode 上跑出来的运行表现我的 Python 版提交运行时间大约在 90 到 110 毫秒内存占用在 LeetCode 的统计里能稳定超过大多数提交。C 版本运行时间在 60 毫秒上下内存优势也很明显。这当然不代表我的代码是全世界最快的但它能说明一个事实增量聚合方案在最坏情况下也是稳定 O(1)不需要任何额外优化。这个方法跑完所有用例之后我特意去看了一眼题目的讨论区。发现很多高票答案和我思路一样但有些人会在getAverageTime里做额外的“如果没有记录怎么办”的判断。其实题目保证了每次查询的路线都至少有一次已完成行程所以这个判断属于防御式编程写了不扣分但面试时别让防御逻辑干扰主流程的清晰度。6.2 把这道题改成你自己的面试练习题可以怎么练刷完 1396 之后我做了一个变体练习把约束稍微改一改看自己能不能扛住追问。第一个变体如果同一个乘客可以同时处于多条行程中比如并发乘车该怎么办这会让check_in表从“id 到一条记录”变成“id 到一组记录”出站时还要考虑该匹配哪一条进站记录。这个问题会让原题的简单性荡然无存但在讨论中能启发你对数据结构选型的思考。第二个变体如果方法调用次数从 2 × 10^4 变成 10^7内存方案还够吗答案是不够需要把聚合值落到分布式存储或消息队列里让多个计算节点各自维护一部分站点对的统计再定期合并。但 LeetCode 范围内不需要考虑这一步我们只需要理解方向。第三个变体如果要求同时回答“A 到 B 的平均时间”和“A 到 B 的中位数时间”原题两张表的设计还够吗不够。平均数可以用累计值推导中位数却必须保留全部样本或者构造分位数近似。这个追问能帮你测试自己是否真的理解了“增量聚合能回答哪些指标”。我自己刷完这道题最大的收获不是记住了“两个哈希表”这个标准答案而是养成了一个习惯拿到任何“设计某某系统”的题先问自己三个问题——查询口径是什么事件流以什么形式进来我能不能在事件发生时就把答案准备好。这三个问题想清楚数据结构基本就自己冒出来了。LeetCode 1396 就是把这三个问题浓缩在了一道题里的绝佳范本值得反复咀嚼。