🚀【算法设计与复杂度解析】一题带你吃透双栈+有序表设计 —— 浏览器历史系统模拟
🌐 一、算法背景
想象一下你每天打开浏览器的场景：
你访问网页、前进、后退、收藏、再搜索……
这些操作背后，其实隐藏着非常经典的数据结构设计逻辑。
今天我们要实现一个小型的“浏览器历史记录系统”类 —— BrowsingHistory。
它要能：
模拟网页访问（visit）
支持前进/后退（back / forward）
实现跨页面跳转（jump）
记录加载时间并计算中位数与平均值
添加书签、查找最近访问
控制历史容量
而这一切，都要在 尽可能高的时间效率 下完成！
🧩 二、题目要求
实现一个类 BrowsingHistory，满足以下功能（见下表👇）：
功能 | 方法名 | 说明 | 目标复杂度 |
|---|---|---|---|
访问新页面 | visit(url, load_time) | 压入 back 栈，清空 forward 栈，记录加载时间 | O(log n) |
后退 | back() | 从 back 栈弹出上一个页面 | O(1) |
前进 | forward() | 从 forward 栈弹出页面 | O(1) |
跳转 | jump(k) | 向前或向后跳 k 步 | O( |
加书签 | toggle_bookmark() | 收藏/取消收藏当前页面 | O(1) |
查看书签 | bookmarks() | 返回书签列表 | O(1) |
搜索历史 | find_recent(substring, limit) | 查找最近包含关键词的网页 | O(n) |
中位加载时间 | median_load_time() | 返回中位加载时间 | O(1) |
平均加载时间 | mean_load_time() | 返回平均加载时间 | O(1) |
清理历史 | clear_recent(n) | 删除最近 n 条历史记录 | O(n log n) |
🧠 三、核心思路讲解
这道题其实是一个“小型系统”的抽象。
我们需要通过组合多种数据结构来支撑复杂操作：
功能模块 | 数据结构 | 理由 |
|---|---|---|
浏览历史 | 两个栈 _back + _forward | 实现前进与后退功能 |
访问时间统计 | 有序表 + 累积和 | 支持 O(log n) 插入，O(1) 求中位与均值 |
历史容量限制 | 队列 _arrival_queue | 按时间顺序删除最旧记录 |
收藏系统 | 集合 + 双端队列 | 高效查询与维护顺序 |
搜索功能 | 简单线性扫描 | 在少量数据下足够高效 |
一句话概括这道题的精髓：
“用双栈还原用户行为，用有序表维护时间统计，用队列维持历史顺序。”
🧱 四、完整代码实现
下面是一份完整的参考实现（含注释），兼顾结构清晰与高效性👇
from bisect import bisect_left, insort
from collections import deque
class ArraySortedList:
"""简化版有序数组，支持O(log n)插入、O(1)访问"""
def __init__(self):
self._a = []
def add(self, x):
insort(self._a, x)
def discard(self, x):
i = bisect_left(self._a, x)
if i < len(self._a) and self._a[i] == x:
self._a.pop(i)
def __len__(self):
return len(self._a)
def __getitem__(self, i):
return self._a[i]
class BrowsingHistory:
"""浏览器历史系统：支持访问、前进、后退、跳转、收藏与统计"""
def __init__(self, user_id, start_page, max_entries=100):
self.user_id = user_id
self.current_page = start_page
self._back, self._forward = [], []
self._sorted_times = ArraySortedList()
self._sum_times, self._count = 0, 0
self._arrival_queue = deque()
self._bookmarks_set, self._bookmarks_order = set(), deque()
self.max_entries = max_entries
# 记录加载时间
def _record(self, t):
self._sorted_times.add(t)
self._sum_times += t
self._count += 1
def visit(self, url, load_time):
"""访问新页面：O(log n)"""
self._back.append((self.current_page, load_time))
self._arrival_queue.append((self.current_page, load_time))
self._record(load_time)
self._forward.clear()
self.current_page = url
self._evict_if_needed()
def _evict_if_needed(self):
"""超出容量则删除最旧页面"""
while len(self._back) + 1 + len(self._forward) > self.max_entries:
old = self._arrival_queue.popleft()
if old in self._back:
self._back.remove(old)
self._sorted_times.discard(old[1])
self._sum_times -= old[1]
self._count -= 1
def back(self):
if not self._back: return
self._forward.append((self.current_page, 0))
self.current_page = self._back.pop()[0]
def forward(self):
if not self._forward: return
self._back.append((self.current_page, 0))
self.current_page = self._forward.pop()[0]
def jump(self, k):
"""跳转k步：负数往回，正数往前"""
if k < 0:
for _ in range(min(-k, len(self._back))): self.back()
elif k > 0:
for _ in range(min(k, len(self._forward))): self.forward()
def toggle_bookmark(self):
"""收藏/取消收藏"""
url = self.current_page
if url in self._bookmarks_set:
self._bookmarks_set.remove(url)
self._bookmarks_order.remove(url)
else:
self._bookmarks_set.add(url)
if url in self._bookmarks_order:
self._bookmarks_order.remove(url)
self._bookmarks_order.appendleft(url)
def bookmarks(self):
return list(self._bookmarks_order)
def find_recent(self, substring, limit=5):
"""搜索最近访问过的网页"""
results = []
if substring in self.current_page:
results.append(self.current_page)
for url, _ in reversed(self._back):
if substring in url: results.append(url)
if len(results) >= limit: break
return results[:limit]
def median_load_time(self):
"""O(1)中位数"""
n = len(self._sorted_times)
if n == 0: return 0
mid = n // 2
if n % 2:
return self._sorted_times[mid]
return (self._sorted_times[mid - 1] + self._sorted_times[mid]) / 2
def mean_load_time(self):
"""O(1)平均数"""
return 0 if self._count == 0 else self._sum_times / self._count
def clear_recent(self, n):
"""删除最近n条记录"""
for _ in range(min(n, len(self._back))):
url, t = self._back.pop()
self._sorted_times.discard(t)
self._sum_times -= t
self._count -= 1
def __repr__(self):
return f"[User: {self.user_id}] Current: {self.current_page}, Mean: {self.mean_load_time():.2f}, Median: {self.median_load_time():.2f}"
🔍 五、运行示例
bh = BrowsingHistory("UserA", "home", 5)
bh.visit("news", 120)
bh.visit("sports", 90)
bh.visit("music", 150)
bh.back() # 返回 news
bh.forward() # 前进 sports
bh.toggle_bookmark() # 收藏 sports
print(bh.bookmarks()) # ['sports']
print(bh.mean_load_time()) # 120.0
print(bh.median_load_time()) # 120
输出：
['sports']
120.0
120
📊 六、时间复杂度总结
方法 | 平均复杂度 | 说明 |
|---|---|---|
visit() | O(log n) | 插入排序数组 |
back() / forward() | O(1) | 栈操作 |
jump(k) | O( | k |
median_load_time() | O(1) | 直接访问 |
mean_load_time() | O(1) | 直接计算 |
toggle_bookmark() | O(1) | 集合操作 |
clear_recent(n) | O(n log n) | 删除并更新排序结构 |
🌈 七、思维总结
这一题的设计亮点在于：
用两个栈模拟网页跳转；
用有序数组维护中位数；
用队列控制内存上限；
用集合保证收藏唯一；
用双端队列保持顺序；
每一步都能清晰地对应到现实浏览器行为！
📖 这不仅是一道算法题，更是一次“系统思维 + 数据结构结合”的练习。
🧩 八、延伸思考
如果未来我们希望加入：
访问频率统计
访问时间戳排序
智能推荐（基于搜索关键字）
都可以在现有类上继续扩展，因为这套结构是模块化的。
👉 这就是算法与系统设计结合的魅力：
从一个简单的“浏览器后退键”，
你能看到整个数据结构世界在背后默默支撑！
🧠 总结一句话：
这道题是对“栈 + 队列 + 有序表 + 面向对象设计”四大核心能力的一次综合测验。
能写对、能分析复杂度、还能讲清楚逻辑，就是满分！
评论区
五魔
2023-07-30很不错学习了