MediumRating 1832

2034. Stock Price Fluctuation

hash-tabledesignheap-priority-queuedata-streamordered-set

在 LeetCode 上作答 ↗

解題說明

Stock Price Fluctuation

題目描述：設計一個股票價格追蹤系統，支援以下操作：更新某時間戳的股價（可能修正之前的價格）、取得最新價格、取得當前最高價格、取得當前最低價格。

解題思路：使用 hash map 記錄每個時間戳對應的價格，搭配一個 multiset（有序集合）來維護所有當前有效的價格。

update(timestamp, price)：若該時間戳已存在舊價格，先從 multiset 中移除舊價格，再插入新價格。同時更新 hash map 和最新時間戳。
current()：回傳最大時間戳對應的價格。
maximum()：回傳 multiset 中的最大值（*rbegin()）。
minimum()：回傳 multiset 中的最小值（*begin()）。

multiset 自動維護排序，插入和刪除都是 O(log n)，完美支援重複價格的情境。

C++ 解法

複雜度分析

時間複雜度：O(log n)（每次操作）— update 涉及 multiset 的插入和刪除各一次；current / maximum / minimum 為 O(1)。

空間複雜度：O(n) — hash map 和 multiset 各存儲 n 個元素。

虛擬碼

1. Maintain a hash map (timestamp -> price) and a multiset of all prices.
2. UPDATE(timestamp, price):
   a. If timestamp exists in map, remove old price from multiset.
   b. Set map[timestamp] = price, insert price into multiset.
   c. Update latestTime = max(latestTime, timestamp).
3. CURRENT(): return map[latestTime].
4. MAXIMUM(): return last element of multiset.
5. MINIMUM(): return first element of multiset.

其他解法

雙堆法（Max-Heap + Min-Heap）：使用最大堆和最小堆分別追蹤最大和最小價格。取極值時用 lazy deletion（若堆頂的時間戳對應價格已過時則彈出）。時間複雜度均攤 O(log n)，但最壞情況下堆中可能累積大量過時元素。
線段樹法：若時間戳範圍有限，可用線段樹直接維護區間最大/最小值。更新 O(log T)，查詢 O(1)，但空間較大且實作複雜。

延伸思考

若還需要支援查詢「某時間區間內的最高/最低價格」，資料結構需要如何修改？
若 update 操作頻率遠高於查詢操作，如何優化以降低 update 的平均時間？
如何擴展系統以支援多支股票的同時追蹤？

Stock Price Fluctuation — CaffeCode