LC.P2034[股票价格波动]

方法一：哈希表+有序集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class StockPrice {

    int cur;
    Map<Integer, Integer> timePriceMap; // key: timestamp   value: price
    TreeMap<Integer, Integer> priceTimeCntMap; // key: price   value: 时间戳数量

    public StockPrice() {
        cur = 0;
        timePriceMap = new HashMap<>();
        priceTimeCntMap = new TreeMap<>();
    }

    public void update(int timestamp, int price) {
        if (timePriceMap.containsKey(timestamp)) {
            Integer oldPrice = timePriceMap.get(timestamp);
            int cnt = priceTimeCntMap.get(oldPrice);
            if (cnt == 1) priceTimeCntMap.remove(oldPrice);
            else priceTimeCntMap.put(oldPrice, cnt - 1);
        }
        timePriceMap.put(timestamp, price);
        priceTimeCntMap.merge(price, 1, Integer::sum);
        cur = Math.max(cur, timestamp);
    }

    public int current() {
        return timePriceMap.get(cur);
    }

    public int maximum() {
        return priceTimeCntMap.lastKey();
    }

    public int minimum() {
        return priceTimeCntMap.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();
 */

  • 时间复杂度：current复杂度为$O(1)$，其余方法复杂度为$O(logn)$，总体复杂度为$O(logn)$

  • 空间复杂度：$O(n)$