LeetCode 1396. 设计地铁系统
题目描述
题意分析
系统记录乘客的进站和出站事件，并查询某个起点站到终点站的历史平均乘车时间。一段完整行程由同一乘客的一次进站和随后的一次出站配对，尚未出站的行程不参与统计。
路线有方向，起点到终点与反向路线分别计算。题目保证调用有效：乘客不会同时处于两段行程中，出站时间晚于对应进站时间，查询路线也已经至少完成过一次行程。
解法：哈希表记录行程
核心思路
[!blue]
需要保存两种生命周期不同的信息。
active按乘客编号记录还未结束的行程，包括起点站和进站时刻；stats按有向路线记录所有已完成行程的累计耗时与次数。前者用于配对事件，后者用于回答历史统计查询。进站只更新在途记录。出站时，用乘客编号取出他的起点和开始时间，计算
出站时刻 - 进站时刻，然后把这段耗时加入对应路线的总和、把次数加一，同时移除在途记录。这样每次完成事件都只结算一段行程，乘客之后也可以重新开始新的行程。平均耗时只取决于总和与次数，不需要保存每条历史明细。查询时返回
total / count，但必须先转为浮点数再除，才能保留小数；也不能把原平均值与新耗时直接二等分，因为旧平均值可能代表多次行程。路线键要同时保留起点、终点和先后顺序。Java 使用
起点 + # + 终点，题目站名只含英文字母和数字，因此分隔符不会与站名内容混淆；Go 使用起终点结构体作为键，直接表达两个字段。累计耗时可能超过一次行程的整数范围，所以使用 64 位保存。Go 的统计值存为结构体，读取 map 得到的是副本，修改后必须写回；Java map 中保存对象引用，更新对象字段即可保留统计结果。
解题步骤
- 创建按乘客编号索引的在途表，以及按有向路线索引的汇总表。
checkIn保存当前乘客的起点站和时刻。checkOut读取并删除在途记录，求出本次耗时，更新对应路线的总耗时与次数。getAverageTime找到路线统计，将总耗时转换为浮点后除以次数并返回。
代码实现
class UndergroundSystem {
private static class CheckInInfo {
final String station;
final int time;
CheckInInfo(String station, int time) {
this.station = station;
this.time = time;
}
}
private static class Stat {
long total;
int count;
}
private final Map<Integer, CheckInInfo> active = new HashMap<>();
private final Map<String, Stat> stats = new HashMap<>();
public void checkIn(int id, String stationName, int t) {
active.put(id, new CheckInInfo(stationName, t));
}
public void checkOut(int id, String stationName, int t) {
// 完成行程时取得并移除在途记录，只结算已出站行程。
CheckInInfo info = active.remove(id);
String key = routeKey(info.station, stationName);
Stat s = stats.computeIfAbsent(key, k -> new Stat());
// 总耗时与次数增量维护，不保存每条历史明细。
s.total += t - info.time;
s.count++;
}
public double getAverageTime(String startStation, String endStation) {
Stat s = stats.get(routeKey(startStation, endStation));
// 先转浮点再除，保留平均值的小数。
return (double) s.total / s.count;
}
private String routeKey(String startStation, String endStation) {
// 路线有方向，使用分隔符避免不同起终站的直接拼接碰撞。
return startStation + "#" + endStation;
}
}
type checkInInfo struct {
station string
time int
}
type stat struct {
total int64
count int64
}
type route struct {
start string
end string
}
type UndergroundSystem struct {
active map[int]checkInInfo
stats map[route]stat
}
func Constructor() UndergroundSystem {
return UndergroundSystem{
active: make(map[int]checkInInfo),
stats: make(map[route]stat),
}
}
func (u *UndergroundSystem) CheckIn(id int, stationName string, t int) {
u.active[id] = checkInInfo{station: stationName, time: t}
}
func (u *UndergroundSystem) CheckOut(id int, stationName string, t int) {
info := u.active[id]
// 取得进站信息后移除在途记录，只结算已完成行程。
delete(u.active, id)
// 用有方向的起终站组合做键，不合并反向路线。
key := route{start: info.station, end: stationName}
s := u.stats[key]
s.total += int64(t - info.time)
s.count++
// map 取出的结构体是副本，更新后要写回。
u.stats[key] = s
}
func (u *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
s := u.stats[route{start: startStation, end: endStation}]
// 先转浮点再除，保留平均值的小数。
return float64(s.total) / float64(s.count)
}
复杂度分析
设站名长度上界为 $L$，过程中最多同时在途人数为 $P$，已完成的不同有向路线数为 $R$。
- 时间复杂度：单次操作期望为 $O(L)$，包括路线键构造及字符串哈希；只看固定长度站名时为期望常数时间。
- 空间复杂度：$O((P+R)L)$，保存未完成行程与每条路线的汇总，不随同一路线的历史行程条数线性增长。
关键点总结
[!green]
- 在途表配对进出站，路线表保留历史总和与次数，两者职责不同。
- 一次行程完成时才计入平均值，反向路线不能合并。
- 总和用宽整数，除法前转浮点；Go 更新结构体副本后需要写回 map。
易错点总结
[!yellow]
- 先做整数除法再转浮点，小数部分已经被截断，无法恢复。
- 起终站直接无分隔拼接，可能让不同的两段名称组合得到相同键。
- 把两方向路线归为同一组，会混淆不同出发站的历史耗时。
- 累计耗时用 32 位保存，重复行程累加后可能溢出。
- Go 修改统计结构体后不写回 map，查询仍会读到旧结果。
- 出站后不移除在途记录，会破坏在途表只表示未完成行程的含义。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1661. 每台机器的进程平均运行时间 | 简单 | 同样先配对开始与结束事件求时长，再按类别累计总时长与次数得到平均值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！