5895. 獲取單值網格的最小操作數
給你一支股票價格的數據流。數據流中每一條記錄包含一個 時間戳?和該時間點股票對應的 價格?。
不巧的是，由于股票市場內在的波動性，股票價格記錄可能不是按時間順序到來的。某些情況下，有的記錄可能是錯的。如果兩個有相同時間戳的記錄出現在數據流中，前一條記錄視為錯誤記錄，后出現的記錄 更正?前一條錯誤的記錄。
請你設計一個算法，實現：
更新 股票在某一時間戳的股票價格，如果有之前同一時間戳的價格，這一操作將?更正?之前的錯誤價格。
找到當前記錄里 最新股票價格?。最新股票價格?定義為時間戳最晚的股票價格。
找到當前記錄里股票的 最高價格?。
找到當前記錄里股票的 最低價格?。
請你實現?StockPrice?類：
- StockPrice()?初始化對象，當前無股票價格記錄。
- void update(int timestamp, int price)?在時間點 timestamp?更新股票價格為 price?。
- int current()?返回股票 最新價格?。
- int maximum()?返回股票 最高價格?。
- int minimum()?返回股票 最低價格?。
示例 1：輸入：
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
輸出：
[null, null, null, 5, 10, null, 5, null, 2]解釋：
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // 時間戳為 [1] ，對應的股票價格為 [10] 。
stockPrice.update(2, 5); // 時間戳為 [1,2] ，對應的股票價格為 [10,5] 。
stockPrice.current(); // 返回 5 ，最新時間戳為 2 ，對應價格為 5 。
stockPrice.maximum(); // 返回 10 ，最高價格的時間戳為 1 ，價格為 10 。
stockPrice.update(1, 3); // 之前時間戳為 1 的價格錯誤，價格更新為 3 。// 時間戳為 [1,2] ，對應股票價格為 [3,5] 。
stockPrice.maximum(); // 返回 5 ，更正后最高價格為 5 。
stockPrice.update(4, 2); // 時間戳為 [1,2,4] ，對應價格為 [3,5,2] 。
stockPrice.minimum(); // 返回 2 ，最低價格時間戳為 4 ，價格為 2 。
解題思路
- void update(int timestamp, int price)?在時間點 timestamp?更新股票價格為 price?。
- int current()?返回股票 最新價格?。
- int maximum()?返回股票 最高價格?。
- int minimum()?返回股票 最低價格?。
我們的目標是實現上述4個方法。
- int current()?返回股票 最新價格。我們只需要維護兩個變量，最大的時間戳以及對應的價格即可
- 而對于其他方法，我們需要讀取的是股票的最低以及最高價格，但是update方法會更正某些時間戳的價格，因此股票的最高和最低價格是動態更新的。使用一個treemap，維護價格和時間戳的對應關系，對于某個價格，該股票可能有多個對應的時間戳，利用treemap的特性我們可以在o（1）的時間復雜度內獲取當前最大和最小價格。我們可以使用map維護每個時間戳對應的價格。
- 而update方法就需要維護上面的兩個map。通過map，我們可以得到需要更新的時間戳原價是多少，再通過這個價格，定位到treemap里面，刪除該時間戳。然后再將該時間戳和價格的對應關系插入到map和treemap里面
代碼
class StockPrice {//timeStamp ->priceMap<Integer, Integer> map = new HashMap<>();//price -> timeStampsTreeMap<Integer, Set<Integer>> up = new TreeMap<>();int curTime=-1,curPrice=-1;public StockPrice() {}public void update(int timestamp, int price) {if (timestamp>=curTime){curTime=timestamp;curPrice=price;}if(map.containsKey(timestamp)){Integer old = map.get(timestamp);up.get(old).remove(timestamp);if (up.get(old).isEmpty())up.remove(old);}map.put(timestamp, price);if (!up.containsKey(price))up.put(price,new HashSet<>());up.get(price).add(timestamp);}public int current() {return curPrice;}public int maximum() {return up.lastKey();}public int minimum() {return up.firstKey();}}/*** Your StockPrice object will be instantiated and called as such:* StockPrice obj = new StockPrice();* obj.update(timestamp,price);* int param_2 = obj.current();* int param_3 = obj.maximum();* int param_4 = obj.minimum();*/
)