MediumRating 1454
1472. Design Browser History
arraylinked-liststackdesigndoubly-linked-listdata-stream
解題說明
Design Browser History
題目描述: 設計一個瀏覽器歷史記錄系統,支援三種操作:
visit(url)— 訪問新頁面。清除當前頁面之後的所有前進歷史。back(steps)— 後退最多 steps 步,回傳當前頁面的 URL。forward(steps)— 前進最多 steps 步,回傳當前頁面的 URL。
解題思路:
使用一個動態陣列(vector)模擬歷史記錄,加上一個指標 cur 表示當前位置。
visit(url):將陣列截斷至 cur+1,然後追加新 URL,cur 加一。back(steps):cur = max(0, cur - steps),回傳 history[cur]。forward(steps):cur = min(lastIndex, cur + steps),回傳 history[cur]。
陣列的方式比雙向鏈結串列更快(快取友好),且操作簡單。
C++ 解法
複雜度分析
時間複雜度:visit O(1) 均攤(resize 可能需要 O(前進歷史長度)),back O(1),forward O(1)。
空間複雜度:O(n) — n 為歷史記錄中的頁面總數。
虛擬碼
1. Initialize history = [homepage], cur = 0 2. visit(url): a. Truncate history to size cur + 1 b. Append url to history c. cur++ 3. back(steps): a. cur = max(0, cur - steps) b. Return history[cur] 4. forward(steps): a. cur = min(history.size() - 1, cur + steps) b. Return history[cur]
其他解法
雙向鏈結串列:每個節點存 URL,使用 prev/next 指標。visit 時斷開後續節點。back/forward 沿指標移動。時間複雜度相同,但鏈結串列的快取效能較差,且實作更繁瑣。
雙堆疊法:一個堆疊存後退歷史,另一個存前進歷史。visit 時清空前進堆疊。back 時從後退堆疊 pop 到前進堆疊。直覺但 back/forward 的時間為 O(steps)。
延伸思考
- 若要限制歷史記錄的最大長度(例如最多 100 頁),如何實現環形緩衝區?
- 若要支援「刪除特定 URL」的功能,哪種資料結構更合適?
- 實際瀏覽器的前進/後退如何處理分支歷史(例如從中間頁面訪問新頁面後還想回到舊的前進歷史)?