GuilinDev

Lc2034

05 August 2008

2034. Stock Price Fluctuation

获得有关特定股票的一系列记录。每条记录都包含一个时间戳和该时间戳对应的股票价格。

不幸的是,由于股票市场的波动性,记录并没有按顺序排列。更糟糕的是,有些记录可能不正确。另一个具有相同时间戳的记录稍后可能会出现在流中,以纠正先前错误记录的价格。

设计一个算法:

在特定时间戳更新股票价格,从时间戳的任何先前记录中更正价格。

根据当前记录查找股票的最新价格。最新价格是记录的最新时间戳的价格。

根据当前记录查找股票的最高价格。

根据当前记录查找股票的最低价格。

实现 StockPrice 类:

StockPrice() 初始化没有价格记录的对象。

void update(int timestamp, int price) 更新给定时间戳的股票价格。

int current() 返回股票的最新价格。

int maximum() 返回股票的最高价格。

int minimum() 返回股票的最低价格。

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
46
47
48
class StockPrice {
    int maxTime;
    HashMap<Integer, Integer> timeToPrices;
    TreeMap<Integer, Integer> pricesToCount;

    public StockPrice() {
        timeToPrices = new HashMap<>();
        pricesToCount = new TreeMap<>();
        maxTime = -1;
    }

    public void update(int timestamp, int price) {
        if (timeToPrices.containsKey(timestamp)) {
            int curprice = timeToPrices.get(timestamp);
            int cnt = pricesToCount.get(curprice);
            if (cnt > 1) {
                pricesToCount.put(curprice, cnt - 1);
            } else {
                pricesToCount.remove(curprice);
            }
        }

        timeToPrices.put(timestamp, price);
        pricesToCount.put(price, pricesToCount.getOrDefault(price, 0) + 1);
        maxTime = Math.max(maxTime, timestamp);
    }

    public int current() {
        return timeToPrices.get(maxTime);
    }

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

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