LeetCode 1472. 设计浏览器历史记录

2023-06-20 HGNULB 约 5 分钟

文章信息 6 个分类 · 6 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 B站

标签

数组 栈 链表 设计 数据流 双向链表

题目描述

✅ 1472. 设计浏览器历史记录

题意分析

维护一个浏览器标签页的访问历史。初始化时只有首页；访问新网址会进入该页，后退和前进分别在已有历史中移动指定步数，若可移动的记录不足，就停在能够到达的边界，并返回最终页面。

后退本身不会删除前进记录，之后仍然可以前进。只有在当前位置访问一个新网址时，当前位置之后的旧分支才全部失效。相同网址再次访问也会形成一次新的历史记录，不能按网址去重。

解法：数组 + 指针

核心思路

[!blue]

用数组按访问路径保存网址，用 current 表示当前页下标，用 last 表示仍然有效的最后一条历史下标。有效历史是数组前缀 [0, last]，始终满足 0 <= current <= last；数组在物理上还可能保存更后面的旧数据，但那些记录已经失效。

后退只需把 current 减去步数，再与零取最大值；前进把它加上步数，再与 last 取最小值。这两个操作只改变当前位置，保留全部有效历史，因此后退之后还能沿原路径前进。

访问新网址时，新记录应放在当前页的后一个位置，所以先把 current 加一。如果数组里已有这个槽位，就覆盖旧记录，否则追加新记录。随后令 last = current，把新页面之后的全部旧历史一次性排除在有效范围之外。

没有必要为了访问新页逐个删除旧尾部，因为所有前进操作都受 last 限制，旧值即使暂时留在数组里也不会被访问。之后继续访问时可以复用这些槽位，超出物理长度才触发追加。首页始终位于下标零，使退到最早页面的边界统一处理。

解题步骤

1. 把首页放到历史数组，current 与 last 都初始化为零。
2. visit(url) 将当前位置加一，覆盖该槽位或追加网址，再令有效末尾等于当前位置。
3. back(steps) 将当前位置更新为 max(0, current - steps)，返回该页。
4. forward(steps) 将当前位置更新为 min(last, current + steps)，返回该页。
5. 后续操作始终使用逻辑有效范围，不把数组的物理末尾当作可前进边界。

代码实现

class BrowserHistory {
    private final List<String> history = new ArrayList<>();
    private int current;
    private int last;

    public BrowserHistory(String homepage) {
        history.add(homepage);
    }

    public void visit(String url) {
        current++;

        if (current < history.size()) {
            history.set(current, url);
        } else {
            history.add(url);
        }

        // 新页面使旧前进分支失效，只更新有效末尾。
        last = current;
    }

    public String back(int steps) {
        current = Math.max(0, current - steps);

        return history.get(current);
    }

    public String forward(int steps) {
        // 前进以有效末尾为界，不能使用数组的物理长度。
        current = Math.min(last, current + steps);

        return history.get(current);
    }
}

type BrowserHistory struct {
    history       []string
    current, last int
}

func Constructor(homepage string) BrowserHistory {
    return BrowserHistory{
        history: []string{
            homepage,
        },
    }
}

func (b *BrowserHistory) Visit(url string) {
    b.current++
    if b.current < len(b.history) {
        b.history[b.current] = url
    } else {
        b.history = append(b.history, url)
    }
    // 新页面使旧前进分支失效，只更新有效末尾。
    b.last = b.current
}

func (b *BrowserHistory) Back(steps int) string {
    b.current -= steps
    if b.current < 0 {
        b.current = 0
    }
    return b.history[b.current]
}

func (b *BrowserHistory) Forward(steps int) string {
    b.current += steps
    // 前进以有效末尾为界，不能使用数组的物理长度。
    if b.current > b.last {
        b.current = b.last
    }
    return b.history[b.current]
}

复杂度分析

• 时间复杂度：后退、前进为 O(1)；访问新页为摊还 O(1)，仅动态数组扩容时单次可能复制已有记录，达到 O(v + 1)。
• 空间复杂度：O(v + 1)，其中 v 是访问新页面的次数，包含首页和数组中保留的有效或失效记录。

关键点总结

[!green]

• 当前页、有效末尾和物理数组长度是三件事，last 才决定前进终点。
• 后退保留前进路径，访问新页才截断旧分支。
• 覆盖已有槽位并移动逻辑边界，可以避免逐条删除旧历史。
• 每次操作完成后都保持 0 <= current <= last。

易错点总结

[!yellow]

• 访问新页后没有更新 last：旧分支仍会被当成可前进历史。
• 按数组长度限制前进：数组可能残留已经失效的网址，必须按有效末尾限界。
• 后退时直接删除后面的记录：会错误地失去本应还能前进的历史。
• 移动步数超过边界时直接访问数组：需要把下标截断到首页或有效末尾。
• 相同网址不再记录：每次访问都是独立历史步骤，不能按字符串值去重。
• Go 修改方法使用值接收者：下标字段的修改无法保留给下次操作，当前实现使用指针接收者。

相似题目

题目	难度	关联与区别
2296. 设计一个文本编辑器	困难	同样维护当前位置及左右内容，本题新增访问清空右侧历史，文本插入通常仍保留右侧文本。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/87645360

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！