05 August 2008
获得有关特定股票的一系列记录。每条记录都包含一个时间戳和该时间戳对应的股票价格。
不幸的是,由于股票市场的波动性,记录并没有按顺序排列。更糟糕的是,有些记录可能不正确。另一个具有相同时间戳的记录稍后可能会出现在流中,以纠正先前错误记录的价格。
设计一个算法:
在特定时间戳更新股票价格,从时间戳的任何先前记录中更正价格。
根据当前记录查找股票的最新价格。最新价格是记录的最新时间戳的价格。
根据当前记录查找股票的最高价格。
根据当前记录查找股票的最低价格。
实现 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();
*/