题目

标题和出处

标题：设计浏览器历史记录

出处：1472. 设计浏览器历史记录

难度

6 级

题目描述

要求

你有一个只支持单个标签页的浏览器，最开始你浏览的网页是 ，你可以访问其他的网站 ，也可以在浏览历史中后退 步或前进 步。

请你实现 类：

• %7D#card=math&code=%5Ctexttt%7BBrowserHistory%28string%20homepage%29%7D&id=S5ss0) 用 初始化浏览器类。
• %7D#card=math&code=%5Ctexttt%7Bvoid%20visit%28string%20url%29%7D&id=XHOvv) 从当前页跳转访问 对应的页面。执行此操作会把浏览历史前进的记录全部删除。
• %7D#card=math&code=%5Ctexttt%7Bstring%20back%28int%20steps%29%7D&id=A2CBd) 在浏览历史中后退 步。如果你只能在浏览历史中后退至多 步且 ，那么你只后退 步。请返回后退至多 步以后的 。
• %7D#card=math&code=%5Ctexttt%7Bstring%20forward%28int%20steps%29%7D&id=ET2yX) 在浏览历史中前进 步。如果你只能在浏览历史中前进至多 步且 ，那么你只前进 步。请返回前进至多 步以后的 。

示例

示例 1：

输入：


输出：

解释：
%3B%7D#card=math&code=%5Ctexttt%7BBrowserHistory%20browserHistory%20%3D%20new%20BrowserHistory%28%22leetcode.com%22%29%3B%7D&id=J4iqB)
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.visit%28%22google.com%22%29%3B%7D&id=uNb3j) // 你原本在浏览 。访问
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.visit%28%22facebook.com%22%29%3B%7D&id=tzXKK) // 你原本在浏览 。访问
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.visit%28%22youtube.com%22%29%3B%7D&id=g4Xd0) // 你原本在浏览 。访问
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.back%281%29%3B%7D&id=qXyow) // 你原本在浏览 ，后退到 并返回
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.back%281%29%3B%7D&id=axZ8g) // 你原本在浏览 ，后退到 并返回
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.forward%281%29%3B%7D&id=zSRqH) // 你原本在浏览 ，前进到 并返回
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.visit%28%22linkedin.com%22%29%3B%7D&id=KwVKA) // 你原本在浏览 。访问
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.forward%282%29%3B%7D&id=Eb7DW) // 你原本在浏览 ，你无法前进任何步数。
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.back%282%29%3B%7D&id=Gg7sR) // 你原本在浏览 ，后退两步依次先到 ，然后到 ，并返回
%3B%7D#card=math&code=%5Ctexttt%7BbrowserHistory.back%287%29%3B%7D&id=DeEkG) // 你原本在浏览 ，你只能后退一步到 ，并返回

数据范围

• 
• 
• 
• 和 都只包含 或者小写英语字母
• 最多调用 次 、 和

解法一

思路和算法

由于浏览器历史记录需要存储相邻的页面记录，因此可以使用链表实现。由于需要同时支持后退和前进操作，因此使用双向链表。

双向链表中的每个结点包含 的信息，表示该结点对应的页面，以及更早的相邻结点 和更新的相邻结点 。

实现中需要记录当前访问的页面的结点 ，所有的操作都是基于 。

初始化时，用 创建一个结点，此时双向链表中只有一个结点， 指向唯一的结点。

对于访问操作，创建一个页面为 的结点 ，然后令 指向 ，令 指向 ，最后令 指向 ，表示当前访问的页面是最新页面。

对于后退操作，将 向 方向移动，直到移动次数达到 次或者 变为 （此时 对应最早访问的页面），然后返回 。

对于前进操作，将 向 方向移动，直到移动次数达到 次或者 变为 （此时 对应最新访问的页面），然后返回 。

代码

class BrowserHistory {
    Node curr;
    public BrowserHistory(String homepage) {
        Node home = new Node(homepage);
        curr = home;
    }
    public void visit(String url) {
        Node node = new Node(url);
        curr.next = node;
        node.prev = curr;
        curr = node;
    }
    public String back(int steps) {
        while (curr.prev != null && steps > 0) {
            curr = curr.prev;
            steps--;
        }
        return curr.url;
    }
    public String forward(int steps) {
        while (curr.next != null && steps > 0) {
            curr = curr.next;
            steps--;
        }
        return curr.url;
    }
}
class Node {
    String url;
    Node prev;
    Node next;
    public Node(String url) {
        this.url = url;
    }
}

复杂度分析

• 时间复杂度：构造方法和访问操作的时间复杂度是 #card=math&code=O%281%29&id=ylij5)，后退和前进操作的时间复杂度是 #card=math&code=O%28%5Ctextit%7Bsteps%7D%29&id=EGf7C)。
• 空间复杂度：#card=math&code=O%28n%29&id=KJofM)，其中 是浏览器历史记录中的页面个数。

解法二

思路和算法

浏览器历史记录的访问和后退操作非常适合用栈实现，只需要使用一个栈即可支持访问和后退操作。对于前进操作，需要在后退操作的同时记录访问过的更新的页面，因此需要使用两个栈。

创建两个栈，分别为后退栈和前进栈，后退栈用于支持访问和后退操作，前进栈用于支持前进操作。对于任何操作，总是保证后退栈的栈顶元素为当前访问的页面。

初始化时，将 入后退栈。

对于访问操作，将 入后退栈，并将前进栈清空，因为当前访问的页面后面没有更新访问的页面。

对于后退操作，将后退栈内的元素依次出栈并入前进栈，直到操作的元素个数达到 个或者后退栈只剩下 个元素，然后返回后退栈的栈顶元素。

对于前进操作，将前进栈内的元素依次出栈并入后退栈，直到操作的元素个数达到 个或者前进栈变为空，然后返回后退栈的栈顶元素。

代码

class BrowserHistory {
    Deque<String> backStack;
    Deque<String> forwardStack;
    public BrowserHistory(String homepage) {
        backStack = new ArrayDeque<String>();
        forwardStack = new ArrayDeque<String>();
        backStack.push(homepage);
    }
    public void visit(String url) {
        backStack.push(url);
        forwardStack.clear();
    }
    public String back(int steps) {
        while (backStack.size() > 1 && steps > 0) {
            forwardStack.push(backStack.pop());
            steps--;
        }
        return backStack.peek();
    }
    public String forward(int steps) {
        while (!forwardStack.isEmpty() && steps > 0) {
            backStack.push(forwardStack.pop());
            steps--;
        }
        return backStack.peek();
    }
}

复杂度分析

• 时间复杂度：构造方法和访问操作的时间复杂度是 #card=math&code=O%281%29&id=TRfqA)，后退和前进操作的时间复杂度是 #card=math&code=O%28%5Ctextit%7Bsteps%7D%29&id=vFJRR)。
• 空间复杂度：#card=math&code=O%28n%29&id=snJdh)，其中 是浏览器历史记录中的页面个数。

解法三

思路和算法

上述两种解法的后退和前进操作的时间复杂度都是 #card=math&code=O%28%5Ctextit%7Bsteps%7D%29&id=ko1sJ)，因为没有下标信息，无法快速定位到目标元素。如果使用动态数组存储浏览器历史记录，则可以使各项操作的时间复杂度都达到 #card=math&code=O%281%29&id=diEm4)。

创建动态数组，同时记录当前下标 和最大下标 ，最大下标表示前进操作时的最后一个下标。

初始化时，将 加入动态数组，将 和 都初始化为 。

对于访问操作，将 加 ，然后将 赋到动态数组的下标 处。特别地，如果动态数组中的元素个数小于或等于更新后的 ，则将 添加到动态数组的末尾，此时动态数组的下标 处的元素即为 。由于当前访问的页面为最新访问的页面，因此令 。

对于后退操作，将 更新为 和 中的最大值，则更新后的 为动态数组中目标页面的下标，返回动态数组的下标 处的元素。

对于前进操作，将 更新为 和 中的最小值，则更新后的 为动态数组中目标页面的下标，返回动态数组的下标 处的元素。

由于动态数组中可以根据下标快速定位元素，因此对于后退和前进操作，首先计算出目标页面的下标，然后根据下标得到目标页面，时间复杂度从 #card=math&code=O%28%5Ctextit%7Bsteps%7D%29&id=VImJy) 降到 #card=math&code=O%281%29&id=y3vmo)。

代码

class BrowserHistory {
    List<String> history;
    int index;
    int end;
    public BrowserHistory(String homepage) {
        history = new ArrayList<String>();
        history.add(homepage);
        index = 0;
        end = 0;
    }
    public void visit(String url) {
        index++;
        if (index < history.size()) {
            history.set(index, url);
        } else {
            history.add(url);
        }
        end = index;
    }
    public String back(int steps) {
        index = Math.max(index - steps, 0);
        return history.get(index);
    }
    public String forward(int steps) {
        index = Math.min(index + steps, end);
        return history.get(index);
    }
}

复杂度分析

• 时间复杂度：构造方法和各项操作的时间复杂度是 #card=math&code=O%281%29&id=Xcq1B)。
• 空间复杂度：#card=math&code=O%28n%29&id=BZzx3)，其中 是浏览器历史记录中的页面个数。