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」的功能，哪種資料結構更合適？
- 實際瀏覽器的前進/後退如何處理分支歷史（例如從中間頁面訪問新頁面後還想回到舊的前進歷史）？