Medium

题目描述

你有一个只有一个标签页的浏览器，一开始你在主页，你可以访问其他的 URL，也可以在历史记录中后退或前进指定的步数。

实现 BrowserHistory 类：

  • BrowserHistory(string homepage) 使用 homepage 初始化浏览器类。
  • void visit(string url) 从当前页面访问 url 对应的页面。执行此操作会把浏览器历史记录中的所有前进记录清除。
  • string back(int steps) 在浏览器历史记录中后退 steps 步。如果你只能在历史记录中后退不到 steps 步，那么你只后退你能后退的步数。请返回后退至多 steps 步以后的 url。
  • string forward(int steps) 在浏览器历史记录中前进 steps 步。如果你只能在历史记录中前进不到 steps 步，那么你只前进你能前进的步数。请返回前进至多 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 函数。

解题思路

这道题可以用多种数据结构来解决：

解法一：双栈（推荐解法）

使用两个栈来模拟浏览器的前进和后退功能：

  • backStack：存储可以后退的页面
  • forwardStack：存储可以前进的页面
  • current：当前页面

核心思路：

  1. 访问新页面：清空前进栈，将当前页面压入后退栈，更新当前页面
  2. 后退：从后退栈弹出页面，将当前页面压入前进栈
  3. 前进：从前进栈弹出页面，将当前页面压入后退栈

解法二：数组+指针

使用一个数组存储所有历史记录，用指针标记当前位置。这种方法在空间使用上更直观，但需要处理数组动态调整的问题。

解法三：双向链表

使用双向链表节点表示每个页面，通过指针移动实现前进后退。这种方法在概念上最贴近实际的浏览器实现。

双栈解法在实现简洁性和时间复杂度方面都有优势，是最推荐的解法。

代码实现

class BrowserHistory {
private:
    stack<string> backStack;
    stack<string> forwardStack;
    string current;
    
public:
    BrowserHistory(string homepage) {
        current = homepage;
    }
    
    void visit(string url) {
        backStack.push(current);
        current = url;
        // 清空前进历史
        while (!forwardStack.empty()) {
            forwardStack.pop();
        }
    }
    
    string back(int steps) {
        while (steps > 0 && !backStack.empty()) {
            forwardStack.push(current);
            current = backStack.top();
            backStack.pop();
            steps--;
        }
        return current;
    }
    
    string forward(int steps) {
        while (steps > 0 && !forwardStack.empty()) {
            backStack.push(current);
            current = forwardStack.top();
            forwardStack.pop();
            steps--;
        }
        return current;
    }
};

class BrowserHistory:

    def __init__(self, homepage: str):
        self.back_stack = []
        self.forward_stack = []
        self.current = homepage

    def visit(self, url: str) -> None:
        self.back_stack.append(self.current)
        self.current = url
        # 清空前进历史
        self.forward_stack.clear()

    def back(self, steps: int) -> str:
        while steps > 0 and self.back_stack:
            self.forward_stack.append(self.current)
            self.current = self.back_stack.pop()
            steps -= 1
        return self.current

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.current)
            self.current = self.forward_stack.pop()
            steps -= 1
        return self.current

public class BrowserHistory {
    
    private Stack<string> backStack;
    private Stack<string> forwardStack;
    private string current;

    public BrowserHistory(string homepage) {
        backStack = new Stack<string>();
        forwardStack = new Stack<string>();
        current = homepage;
    }
    
    public void Visit(string url) {
        backStack.Push(current);
        current = url;
        // 清空前进历史
        forwardStack.Clear();
    }
    
    public string Back(int steps) {
        while (steps > 0 && backStack.Count > 0) {
            forwardStack.Push(current);
            current = backStack.Pop();
            steps--;
        }
        return current;
    }
    
    public string Forward(int steps) {
        while (steps > 0 && forwardStack.Count > 0) {
            backStack.Push(current);
            current = forwardStack.Pop();
            steps--;
        }
        return current;
    }
}

var BrowserHistory = function(homepage) {
    this.backStack = [];
    this.forwardStack = [];
    this.current = homepage;
};

BrowserHistory.prototype.visit = function(url) {
    this.backStack.push(this.current);
    this.current = url;
    // 清空前进历史
    this.forwardStack = [];
};

BrowserHistory.prototype.back = function(steps) {
    while (steps > 0 && this.backStack.length > 0) {
        this.forwardStack.push(this.current);
        this.current = this.backStack.pop();
        steps--;
    }
    return this.current;
};

BrowserHistory.prototype.forward = function(steps) {
    while (steps > 0 && this.forwardStack.length > 0) {
        this.backStack.push(this.current);
        this.current = this.forwardStack.pop();
        steps--;
    }
    return this.current;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
visitO(1)O(1)
backO(min(steps, 历史记录数))O(1)
forwardO(min(steps, 前进记录数))O(1)
总空间复杂度-O(n)，n为访问过的页面总数

相关题目