2034. Stock Price Fluctuation

T: O(nlogn), O(1), O(1), O(1)

S: O(n)

class StockPrice {
    private Map<Integer, Integer> timeMap;
    private TreeMap<Integer, Set<Integer>> priceMap;
    private int latestTime;
    public StockPrice() {
        this.timeMap = new HashMap<>();
        this.priceMap = new TreeMap<>();
    }
    // O(logn) -> call n times, so O(nlogn)
    public void update(int timestamp, int price) {
        if (timeMap.containsKey(timestamp)) {
            int prevPrice = timeMap.get(timestamp);
            priceMap.get(prevPrice).remove(timestamp);
            if (priceMap.get(prevPrice).isEmpty()) {
                priceMap.remove(prevPrice);
            }
        }
        timeMap.put(timestamp, price);
        priceMap.computeIfAbsent(price, k -> new HashSet<>()).add(timestamp);
        latestTime = Math.max(latestTime, timestamp);
    }
    
    // O(1)
    public int current() {
        return timeMap.get(latestTime);
    }
    
    // O(1)
    public int maximum() {
        return priceMap.lastKey();
    }
    
    // O(1)
    public int minimum() {
        return priceMap.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();


 latest price -> use variable or 

timestamp, int price

if update timestamp-> use price to find List<Time> -> remove that time, if list empty -> remove price
-> add price, List<time>
 price use treeMap
 */

notice this Question just aims for a particular stock

    // O(1)
    public int current() {
        return timeMap.get(latestTime);
    }
    
    // O(1)
    public int maximum() {
        return priceMap.lastKey();
    }
    
    // O(1)
    public int minimum() {

S: O(n), n is num of stocks

class StockPrice {
    // 
    /*
    注意這題是針對“單一的”股票, 所以沒有什麼 key, quote 的問題
    aim for a particular stock, just one stock
    
    hashMap with latest time variables, 就不用用到 treeMap, current 可以在 O(1) 完成
    但 maxPrice, minPrice
    價格想要有序, 這裡會有點麻煩, 不是靠變數就能解決
    因為價格在同一個時間是會波動的, 會修正
    所以光是紀錄 max, 也不知道這個 max 是哪個時間, 哪個 price 來的
    
    所以紀錄一個 TreeMap 的有序價格表, 是比較簡單的做法, 紀錄<price, count>
    最後回傳最大最小 O(logn)
    這裡用 hashMap 不會比較快, 因為要找最大最小要 O(n)
    
    ["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]
     
     1 10 => 3
     2 5
     4 2
     
     所以可以看到, 因為要更新之前某 time, price 那一定用 hashmap 比較方便, 但 hashmap 如果要求 max, min就很麻煩
     所以可以想到可以用 treeMap
     
     比較簡單的想法是 一個 hashmap 維持正常資料: time, 最新股價
     另一個 treemap 維持 歷史股價, 也可以方便取得 max, min
    
    */
    Map<Integer, Integer> timeMap;  // <time, price>
    TreeMap<Integer, Integer> priceMap; // <price, count>
    int latestTime = 0;
    
    public StockPrice() {
        timeMap = new HashMap<>();
        priceMap = new TreeMap<>();
    }
    // O(logn)
    public void update(int timestamp, int price) {
        if (timeMap.containsKey(timestamp)) { // 代表要更新歷史股價, old price 需要更動, 要刪除
            int oldPrice = timeMap.get(timestamp);
            priceMap.put(oldPrice, priceMap.get(oldPrice) - 1);
            if (priceMap.get(oldPrice) == 0) {
                priceMap.remove(oldPrice);
            }
        }
        timeMap.put(timestamp, price); // 更新最新股價
        latestTime = Math.max(latestTime, timestamp);
        priceMap.put(price, priceMap.getOrDefault(price, 0) + 1); // 歷史股價紀錄最新的 price
    }
    
    
    // O(1)
    public int current() {
        return timeMap.get(latestTime);
    }
    
    // O(1)
    public int maximum() {
        return priceMap.lastKey();
    }
    
    // O(1)
    public int minimum() {
        return priceMap.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();
 */