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

2023-06-20 HGNULB 约 8 分钟

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

分类

题目描述

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

题意分析

要实现一个浏览器的历史记录，构造时给定主页 homepage，然后支持三个操作：visit(url) 从当前页跳到新页；back(steps) 后退最多 steps 步；forward(steps) 前进最多 steps 步。后两个操作都要返回停留在哪个页面。

最容易被忽略、也最能区分做没做过的一条语义是：visit 会把当前页之后的全部前进历史清空。这就是真实浏览器的行为——你后退几步再打开一个新链接，原来的「前进」按钮就灰掉了。题面里写的是「浏览前进历史记录全部删除」，这句话直接决定了数据结构的选型。

第二条语义是「最多」：back(steps) 时若前面不足 steps 页，就退到最前面那一页（主页方向的第一条记录）并返回它，不是报错也不是返回空。forward 同理，撞到最新一条就停下。所以两个操作本质上是「移动后夹紧到合法区间」。

约束里的信号：调用总数到 $5 \times 10^3$，steps 到 100，URL 长度到 20。规模很小，任何 $O(\text{steps})$ 甚至 $O(n)$ 的单次操作都能过——这题考的不是复杂度，是状态维护的正确性。也正因为如此，面试官更可能追问「为什么选数组不选双向链表」「visit 的删除代价怎么算」这类设计权衡问题。

边界：构造后立刻 back(1) 应返回主页；构造后立刻 forward(1) 也应返回主页；visit 之后立刻 forward 必须返回当前页（前进历史刚被清空）；连续 visit 后再一次性 back 一个超大的 steps，要停在主页。

解法：数组 + 指针

核心思路

先想直觉方案：用两个栈，一个存后退历史、一个存前进历史，当前页单独存。back 就是从后退栈弹一个、把当前页压进前进栈。这套写法能work，visit 时把前进栈整个清空也很自然。但它的问题是当前页游离在两个栈之间，每次移动都要在三处同时改状态，steps 超界时的夹紧逻辑还得手写循环，出错面很大。

换个角度观察：后退栈、当前页、前进栈拼起来就是一条线性的浏览序列。直接用动态数组保存页面，再用 current 标记当前位置、last 标记有效历史末尾，状态更集中，移动也能直接用下标完成。

为了让三个操作都保持常数时间，再增加一个有效末尾指针 last。不变量是：history[0..last] 是当前有效历史，current 指向当前页，恒有 0 <= current <= last < history.size()；last 之后即使还有旧值也已失效，任何操作都不能访问。

back(steps)：current = max(0, current - steps)。

forward(steps)：current = min(last, current + steps)，上界必须是有效末尾而不是数组物理末尾。

visit(url)：移动到 current + 1，该位置存在就覆盖，否则追加；最后令 last = current。降低有效末尾就等价于清空全部前进历史，旧槽位无需物理删除。

正确性可以直接由不变量验证：后退和前进只在 [0,last] 内移动，不改变历史；访问新页后，新页位于 current，并令 last = current，所以原前进区间全部落到有效范围之外。三个操作结束后不变量都保持成立，返回的 history[current] 就是实际停留页面。

解题步骤

构造函数：把 homepage 放在下标 0，current = last = 0。

visit(url)：先把 current 加一；若该槽位已分配就覆盖旧值，否则追加；再令 last = current。覆盖只是复用空间，真正让旧前进历史失效的是更新 last。

back(steps)：把 current 减去 steps 后夹到 0，返回移动后的页面。

forward(steps)：把 current 加上 steps 后夹到 last。不能使用 history.size() - 1，因为数组尾部可能保存已失效的旧前进历史。

以题目样例走一遍：BrowserHistory("leetcode.com")，然后依次 visit("google.com")、visit("facebook.com")、visit("youtube.com")、back(1)、back(1)、forward(1)、visit("linkedin.com")、forward(2)、back(2)、back(7)。

构造：history = [leetcode]，current = last = 0。
visit(google)：追加到下标 1，current = last = 1。
visit(facebook)：追加到下标 2，current = last = 2。
visit(youtube)：追加到下标 3，current = last = 3。
back(1)：current = max(0, 3-1) = 2，返回 facebook。
back(1)：current = 1，返回 google。
forward(1)：current = min(last, 1+1) = 2，返回 facebook。
visit(linkedin)：移动到下标 3 并覆盖 youtube，再令 last = 3；有效历史变为 [leetcode, google, facebook, linkedin]。
forward(2)：current = min(last, 3+2) = 3，返回 linkedin，不会越过有效末尾。
back(2)：current = 1，返回 google。
back(7)：current = 0，返回 leetcode。步数超过可退范围时仍停在主页。

输出序列为 facebook, google, facebook, linkedin, google, leetcode，与期望一致。

代码实现

import java.util.ArrayList;
import java.util.List;

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]
}

复杂度分析

时间复杂度：back、forward 都是 $O(1)$；visit 覆盖旧槽位时是 $O(1)$，追加触发动态数组扩容时单次为 $O(n)$、均摊为 $O(1)$。

空间复杂度：$O(v)$，其中 $v$ 是 visit 调用次数。数组长度最多增长一次每次访问；失效槽位保留并复用，不影响渐进上界。

关键点总结

浏览历史本质是一条线性序列；数组负责存页面，current 和 last 分别表示当前位置与有效末尾。

核心不变量是 0 <= current <= last < history.size()，且只有 [0,last] 可访问。物理数组长度不能代替逻辑有效长度。

「最多 steps 步」= 夹紧（clamp），不是循环。一行 max/min 同时覆盖了正常情况和越界情况，比 while 递减更不容易写错。

visit 不必物理删除：覆盖 current+1 并令 last=current，就能让旧前进区间在逻辑上立即失效。

双向链表也能表达历史，但 back(steps) 和 forward(steps) 需要逐步移动；数组下标可以一次夹紧，更适合本题接口。

易错点总结

visit 后忘记令 last = current：依次访问 a,b,c，后退 2 步到 a，再访问 x；此时 c 必须失效。若 last 仍指向旧末尾，forward(10) 会错误前进到 c。

forward 用 history.size()-1 作为上界：数组尾部可能是已失效的旧记录；上例会越过 x 访问 c。逻辑上界必须是 last。

visit 忘记先移动 current：会覆盖当前页本身，导致后退时少一条历史。

back 忘记与 0 取最大：构造后立刻 back(7)，下标变为负数，Java 抛异常、Go panic。

构造函数没把 homepage 放进 history：history 为空时任何 back 都会越界；即使 visit 之后能用，也永远回不到主页。

返回移动前的页面：先取 history.get(current) 再修改 current，样例第一次 back(1) 会错误返回 youtube，正确答案是 facebook。

Go 里用值接收者：current、last 的修改只发生在结构体副本上，连续操作无法维持状态；三个方法都必须使用指针接收者。

相似题目

题目	难度	考察点
146. LRU 缓存	中等	需要哈希表与双向链表两份结构同步维护，容量淘汰是额外的不变量
155. 最小栈	中等	在栈的基础上额外维护历史最小值，考察「辅助状态随主结构同进同退」
232. 用栈实现队列	简单	两个栈之间的元素搬移时机，均摊复杂度分析是核心考点
380. O(1) 时间插入、删除和获取随机元素	中等	数组与哈希表互指，删除时用「与末尾交换」保持数组紧凑
707. 设计链表	中等	纯指针操作，考察哨兵节点与各类下标越界的边界处理
622. 设计循环队列	中等	固定容量下用取模移动双指针，难点在区分队空与队满