从零实现浏览器历史记录功能：力扣1472题深度解析

一、问题理解与应用场景

浏览器历史记录功能是我们日常上网时最常用的功能之一。力扣1472题要求我们模拟实现浏览器的三个核心功能：访问新页面(visit)、后退(bACk)和前进(forward)。这道题很好地展现了如何用数据结构模拟真实世界场景。

二、完整代码实现与注释

class BrowserHistory {
private:
    vector<string> history;  // 使用vector存储所有访问记录
    int current;             // 当前位置索引
    int last;                // 最后有效位置索引

public:
    // 构造函数：初始化浏览器主页
    BrowserHistory(string homepage) {
        history.push_back(homepage);  // 添加主页到历史记录
        current = 0;                  // 初始位置为0
        last = 0;                     // 初始最后位置也是0
    }
    
    // 访问新URL
    void visit(string url) {
        // 如果当前位置不在末尾，需要删除后面的历史记录
        if (current < (int)history.size() - 1) {
            history.erase(history.begin() + current + 1, history.end());
        }
        history.push_back(url);  // 添加新URL
        current++;               // 当前位置后移
        last = current;          // 更新最后有效位置
    }
    
    // 后退功能
    string back(int steps) {
        // 计算后退后的位置，不能小于0
        current = max(0, current - steps);
        return history[current];  // 返回对应URL
    }
    
    // 前进功能
    string forward(int steps) {
        // 计算前进后的位置，不能超过最后有效位置
        current = min(last, current + steps);
        return history[current];  // 返回对应URL
    }
};

三、核心设计思路解析

1. 数据结构选择：使用vector存储历史记录，因为需要频繁的随机访问和尾部插入

2. 关键变量：

• current：标记当前所在页面位置

• last：标记历史记录的有效末尾

3. 边界处理：

• 后退时不能小于0

• 前进时不能超过last

• 访问新页面时清理后续历史记录

四、复杂度分析

1. 时间复杂度：

• visit操作最坏情况O(n)（需要删除元素）

• back和forward操作都是O(1)

2. 空间复杂度：O(n)，n为历史记录数量

五、扩展思考

1. 如何实现历史记录大小限制？

2. 如何添加历史记录搜索功能？

3. 使用双向链表实现的优缺点比较