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

Categories:

题目描述
思路分析
1. 解法一：数组 + 指针（推荐）
相似题目

题目描述

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

思路分析

解法一：数组 + 指针（推荐）

核心思路：

使用列表保存历史记录，idx 指向当前页面。

visit 时截断后续记录并追加新页面。

back/forward 只调整 idx。

复杂度分析：

时间复杂度：O(1) 均摊。

空间复杂度：O(n)。

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

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

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

    public void visit(String url) {
        while (history.size() > idx + 1) {
            history.remove(history.size() - 1);
        }
        history.add(url);
        idx = history.size() - 1;
    }

    public String back(int steps) {
        idx = Math.max(0, idx - steps);
        return history.get(idx);
    }

    public String forward(int steps) {
        idx = Math.min(history.size() - 1, idx + steps);
        return history.get(idx);
    }
}

type BrowserHistory struct {
    history []string
    idx     int
}

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

func (b *BrowserHistory) Visit(url string) {
    b.history = b.history[:b.idx+1]
    b.history = append(b.history, url)
    b.idx = len(b.history) - 1
}

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

func (b *BrowserHistory) Forward(steps int) string {
    b.idx += steps
    if b.idx >= len(b.history) {
        b.idx = len(b.history) - 1
    }
    return b.history[b.idx]
}

相似题目

题目	难度	考察点
146. LRU 缓存	中等	设计
155. 最小栈	中等	设计
232. 用栈实现队列	简单	设计
706. 设计哈希映射	简单	设计
622. 设计循环队列	中等	设计

本文作者: HGNULB

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