LeetCode 1472.设计浏览器历史记录：一个数组完成模拟，单次操作均O(1)

【LetMeFly】1472.设计浏览器历史记录：一个数组完成模拟，单次操作均O(1)

力扣题目链接：https://leetcode.cn/problems/design-browser-history/

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 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 <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage 和 url 都只包含 '.' 或者小写英文字母。
• 最多调用 5000 次 visit， back 和 forward 函数。

解题方法：数组模拟

使用一个大小可变的数组模拟浏览器(标签页)历史记录。初始值只有一个元素homepage。

使用now变量记录当前页面的下标，使用right记录最后一个页面的下标。

同时做到：历史记录数组只增不减，要减小就左移right指针。这样能避免一些重复开辟和释放空间带来的性能损耗。

visit：

1. now++

   如果now超过了历史记录数组的大小，则将当前页面push到历史记录数组中

   否则，直接将history[now]记为当前页面

2. right = now。这是因为一旦访问新页面，则无法再“forward”

   并不需要真的将“无法forward到的页面”从数组中移除，直接等待新访问页面将其覆盖即可

back：

now = max(0, now - step)，然后直接返回history[now]

forward：

now = min(right, now + step)，然后直接返回history[now]

• 时间复杂度$O(N^2)$
• 空间复杂度$O(N\log N)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-02-26 13:16:28* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-26 13:37:36*/
class BrowserHistory {
private:vector<string> history;int now, right;
public:BrowserHistory(string homepage) {history.push_back(homepage);now = right = 0;}void visit(string url) {if (++now == history.size()) {history.push_back(url);} else {history[now] = url;}right = now;}string back(int steps) {now = max(0, now - steps);return history[now];}string forward(int steps) {now = min(right, now + steps);return history[now];}
};/*** Your BrowserHistory object will be instantiated and called as such:* BrowserHistory* obj = new BrowserHistory(homepage);* obj->visit(url);* string param_2 = obj->back(steps);* string param_3 = obj->forward(steps);*/

• 执行用时分布14ms击败92.71%
• 消耗内存分布60.61MB击败96.09%

Python

'''
Author: LetMeFly
Date: 2025-02-26 13:38:49
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-26 13:41:11
'''
class BrowserHistory:def __init__(self, homepage: str):self.history = [homepage]self.now = self.right = 0def visit(self, url: str) -> None:self.now += 1if self.now == len(self.history):self.history.append(url)else:self.history[self.now] = urlself.right = self.nowdef back(self, steps: int) -> str:self.now = max(0, self.now - steps)return self.history[self.now]def forward(self, steps: int) -> str:self.now = min(self.right, self.now + steps)return self.history[self.now]# 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)

Java

/** @Author: LetMeFly* @Date: 2025-02-26 13:41:42* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-26 13:45:07*/
import java.util.List;
import java.util.ArrayList;class BrowserHistory {private List<String> history;private int now, right;public BrowserHistory(String homepage) {history = new ArrayList<>();now = right = 0;history.add(homepage);}public void visit(String url) {if (++now == history.size()) {history.add(url);} else {history.set(now, url);}right = now;}public String back(int steps) {now = Math.max(0, now - steps);return history.get(now);}public String forward(int steps) {now = Math.min(right, now + steps);return history.get(now);}
}/*** Your BrowserHistory object will be instantiated and called as such:* BrowserHistory obj = new BrowserHistory(homepage);* obj.visit(url);* String param_2 = obj.back(steps);* String param_3 = obj.forward(steps);*/

Go

/** @Author: LetMeFly* @Date: 2025-02-26 13:45:43* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-26 13:49:00*/
package maintype BrowserHistory struct {history []stringnow,right int
}func Constructor(homepage string) BrowserHistory {history := make([]string, 1)history[0] = homepagereturn BrowserHistory{history: history,now: 0,right: 0,}
}func (this *BrowserHistory) Visit(url string)  {this.now++if this.now == len(this.history) {this.history = append(this.history, url)} else {this.history[this.now] = url}this.right = this.now
}func (this *BrowserHistory) Back(steps int) string {this.now = max(0, this.now - steps)return this.history[this.now]
}func (this *BrowserHistory) Forward(steps int) string {this.now = min(this.right, this.now + steps)return this.history[this.now]
}/*** Your BrowserHistory object will be instantiated and called as such:* obj := Constructor(homepage);* obj.Visit(url);* param_2 := obj.Back(steps);* param_3 := obj.Forward(steps);*/

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源