LeetCode 题解工作台
设计浏览器历史记录
你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。 请你实现 BrowserHistory 类： BrowserHistory(string homepage) ，用 home…
6
题型
4
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们可以使用两个栈 和 分别存储浏览后退页面和前进页面。初始时 包含 ，而 为空。 调用 时，我们将 加入 ，并清空 。时间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。
请你实现 BrowserHistory 类：
BrowserHistory(string homepage)，用homepage初始化浏览器类。void visit(string url)从当前页跳转访问url对应的页面 。执行此操作会把浏览历史前进的记录全部删除。string back(int steps)在浏览历史中后退steps步。如果你只能在浏览历史中后退至多x步且steps > x，那么你只后退x步。请返回后退 至多steps步以后的url。string forward(int steps)在浏览历史中前进steps步。如果你只能在浏览历史中前进至多x步且steps > x，那么你只前进x步。请返回前进 至多steps步以后的url。
示例：
输入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com"); // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com"); // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com"); // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1); // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1); // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1); // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com"); // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2); // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2); // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7); // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"
提示：
1 <= homepage.length <= 201 <= url.length <= 201 <= steps <= 100homepage和url都只包含 '.' 或者小写英文字母。- 最多调用
5000次visit，back和forward函数。
解题思路
方法一：双栈
我们可以使用两个栈 和 分别存储浏览后退页面和前进页面。初始时 包含 ，而 为空。
调用 时，我们将 加入 ，并清空 。时间复杂度 。
调用 时，我们将 的栈顶元素弹出并加入 ，重复这一操作 次，直到 的长度为 或者 为 。最后返回 的栈顶元素。时间复杂度 。
调用 时，我们将 的栈顶元素弹出并加入 ，重复这一操作 次，直到 为空或者 为 。最后返回 的栈顶元素。时间复杂度 。
空间复杂度 ，其中 是浏览历史记录的长度。
class BrowserHistory:
def __init__(self, homepage: str):
self.stk1 = []
self.stk2 = []
self.visit(homepage)
def visit(self, url: str) -> None:
self.stk1.append(url)
self.stk2.clear()
def back(self, steps: int) -> str:
while steps and len(self.stk1) > 1:
self.stk2.append(self.stk1.pop())
steps -= 1
return self.stk1[-1]
def forward(self, steps: int) -> str:
while steps and self.stk2:
self.stk1.append(self.stk2.pop())
steps -= 1
return self.stk1[-1]
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity for visit, back, and forward operations is O(1) per move if using a doubly-linked list with pointers, or O(steps) if using stacks. Space complexity is O(n) for storing up to n visited URLs, regardless of approach. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
You may be asked to justify linked-list vs stack trade-offs.
- question_mark
Clarify whether forward history should be cleared on new visits.
- question_mark
Expect questions about optimizing back and forward operations for large histories.
常见陷阱
外企场景- error
Not clearing forward history after a new visit.
- error
Using a singly-linked list which makes back operation inefficient.
- error
Incorrectly updating current pointer when moving back or forward multiple steps.
进阶变体
外企场景- arrow_right_alt
Implement BrowserHistory with circular doubly-linked list for memory reuse.
- arrow_right_alt
Use array-based dynamic structure to simulate stacks for back and forward.
- arrow_right_alt
Extend to multi-tab browsing with separate histories per tab.