LeetCode 1396. 设计地铁系统

约 7 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里巴巴
标签
字符串 哈希表 设计
目录

题目描述

✅ 1396. 设计地铁系统

题意分析

要实现一个类，支持三个操作：checkIn(id, stationName, t) 表示编号 id 的乘客在 t 时刻从 stationName 进站；checkOut(id, stationName, t) 表示他在 t 时刻从 stationName 出站；getAverageTime(startStation, endStation) 返回历史上所有「从 startStation 进、从 endStation 出」的行程的平均耗时。

题目明确给出两条极其有用的保证：一个乘客在任意时刻最多只有一次未完成的行程（进站后必然先出站才会再次进站），并且查询的那对站点一定至少发生过一次行程。前者意味着「乘客 → 进站信息」是一对一的映射，不需要维护队列或列表；后者意味着查询时不用处理除零。这两条把实现难度砍掉了一大半，读题时必须抓住。

三个操作里，checkIn 是「记录待配对的半条记录」，checkOut 是「配对成功并结算」，getAverageTime 是「读取已结算的汇总」。识别出这个三段式，数据结构就自然浮现了。

平均耗时的定义是「所有该线路行程耗时之和 ÷ 行程次数」，所以只需要维护累计和与计数两个数，不需要保存每一条行程明细。这是本题最重要的空间优化——保存明细会让 getAverageTime 退化成 $O(k)$ 的遍历。

约束里三个方法的总调用次数最多 $2 \times 10^4$，站名长度不超过 10，t 严格递增且不超过 $10^9$。调用量不大，但要求每个操作都是 $O(1)$ 的均摊复杂度。t 上界 $10^9$、行程数上界 $2 \times 10^4$，两者相乘可达 $2 \times 10^{13}$，超出 32 位整数范围，累计和必须用 64 位类型。

边界要留意四点：起点和终点可以是同一个站（乘客进站后原地出站）；不同乘客的行程互不干扰；同一对站点的多次行程要累加进同一个统计项；平均值要返回浮点数，整数除法会截断。

解法：哈希表记录行程

核心思路

两类信息的生命周期不同，需要两个哈希表：

  • active[id] = (startStation, checkInTime) 保存尚未结束的行程；
  • stats[route] = (totalTime, tripCount) 保存已完成线路的累计耗时与次数。

路线键必须是有方向的有序对 (startStation, endStation)。Java 用站名中不可能出现的 # 分隔后拼接，Go 直接使用可比较的结构体作为键。不能直接无分隔拼接：("AB","C") 与 ("A","BC") 都会变成 "ABC"；也不能对站名排序，因为反向路线的统计彼此独立。

checkIn 只登记在途信息。checkOut 取出并删除该乘客的进站记录，计算耗时，然后更新对应路线的 totalTime 和 tripCount。平均值只依赖这两个聚合量，无需保存所有行程明细。

两个不变量贯穿所有操作：active 恰好包含当前未出站乘客；每个 stats[route] 恰好汇总该路线全部已完成行程。于是查询时直接计算 totalTime / tripCount 就是正确平均值。累计耗时使用 64 位整数，除法前转换为浮点数以保留小数。

解题步骤

  1. checkIn：以乘客 id 为键记录起点与进站时间。
  2. checkOut：删除并取得进站信息，以有方向的起终点生成路线键。
  3. 将 t - checkInTime 累加到该路线总耗时，并把次数加一。
  4. getAverageTime：查出路线统计，返回浮点除法结果。

示例中 Leyton -> Waterloo 的前两次耗时是 12 和 10，统计量为 (22,2)，平均值 11；第三次耗时 14 完成后变为 (36,3)，平均值 12。尚未 checkOut 的行程始终只在 active 中，不会污染平均值。

路线键反例：AB -> C 与 A -> BC 必须分开；A -> B 与 B -> A 也必须分开。

代码实现

import java.util.HashMap;
import java.util.Map;

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++
	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)
}

复杂度分析

  • 时间复杂度：三个操作的哈希表访问均为期望 $O(1)$；计入长度为 $L$ 的站名哈希或 Java 路线键构造，则为 $O(L)$。
  • 空间复杂度：哈希表共有 $O(P+R)$ 个条目，其中 $P$ 是同时在途乘客数，$R$ 是出现过的有向路线数；若计入平均长度为 $L$ 的站名与路线键内容，则为 $O((P+R)L)$。只保存汇总，不随已完成行程总数继续增长。

关键点总结

  • 在途行程按乘客编号存储，完成时立即删除，状态与题意一一对应。
  • 平均值可由总耗时与次数增量维护，查询无需扫描历史明细。
  • 路线是有方向的复合键；编码时要防拼接碰撞。
  • 累计耗时使用 64 位，平均值计算前转换为浮点数。
  • 题目保证操作合法且查询路线已有数据，因此无需额外错误分支。

易错点总结

  • 累计耗时使用 32 位整数可能溢出；单次时间合法不代表多次累加仍合法。
  • 整数除法会截断小数。总耗时 11、次数 2 的答案应为 5.5，而不是 5。
  • 路线键不带分隔符时，("AB","C") 与 ("A","BC") 会碰撞。
  • 把路线当成无向边会合并 A -> B 与 B -> A，违背题意。
  • checkOut 后不删除乘客，会破坏“在途表只含未完成行程”的不变量。
  • Go 从 map 取出结构体得到副本，修改统计量后必须写回 map。

相似题目

题目 难度 考察点
1146. 快照数组 中等 同为「写入时记录、查询时读取」，但要按版本号二分查找历史值
362. 敲击计数器 中等 时间窗口内的计数统计，需要环形数组或队列淘汰过期记录
355. 设计推特 中等 多个哈希表配合（用户关系 + 推文列表），查询时用堆做多路归并
146. LRU 缓存 中等 哈希表 + 双向链表实现 $O(1)$ 读写与淘汰，设计题的必会模板
460. LFU 缓存 困难 在 LRU 基础上再按频次分桶，需要三层结构维护 $O(1)$
380. O(1) 时间插入、删除和获取随机元素 中等 数组 + 哈希表互相索引，训练「用两个结构互补」的设计直觉
432. 全 O(1) 的数据结构 困难 计数与最值同时 $O(1)$，靠按计数分组的双向链表实现
155. 最小栈 中等 用辅助栈同步维护聚合量，与本题「增量维护聚合而非重算」同源
716. 最大栈 困难 在最小栈基础上要求删除任意最大元素，需要有序结构配合
295. 数据流的中位数 困难 中位数无法用单个聚合量增量维护，必须用双堆，正好对照本题平均值的可增量性
703. 数据流中的第 K 大元素 简单 用固定大小的小顶堆在线维护第 K 大，同属流式统计
232. 用栈实现队列 简单 均摊 $O(1)$ 的经典设计，训练对「均摊复杂度」的分析
705. 设计哈希集合 简单 手写哈希表本体，理解本题所依赖的底层结构
208. 实现 Trie (前缀树) 中等 字符串键的另一种组织方式，可对比「拼接字符串当键」的取舍