股票价格波动
难度:
标签:
题目描述
代码结果
运行时间: 423 ms, 内存: 62.7 MB
/* 思路:使用Stream来处理集合的最大值和最小值查找。仍然使用HashMap来存储时间戳和价格的映射。 */
import java.util.HashMap;
import java.util.Map;
class StockPrice {
private Map<Integer, Integer> timestampPriceMap;
private int latestTimestamp;
public StockPrice() {
timestampPriceMap = new HashMap<>();
latestTimestamp = 0;
}
public void update(int timestamp, int price) {
if (timestamp >= latestTimestamp) {
latestTimestamp = timestamp;
}
timestampPriceMap.put(timestamp, price);
}
public int current() {
return timestampPriceMap.get(latestTimestamp);
}
public int maximum() {
return timestampPriceMap.values().stream().mapToInt(v -> v).max().getAsInt();
}
public int minimum() {
return timestampPriceMap.values().stream().mapToInt(v -> v).min().getAsInt();
}
}
解释
方法:
该题解采用堆和哈希表结合的方式来维护股票价格的数据流。堆用于快速检索最大和最小价格,哈希表用于记录每个时间戳对应的价格,并跟踪最新价格。具体来说,使用两个堆,一个最大堆(存储负值以模拟最大堆)用来找到最大价格,一个最小堆用来找到最小价格。更新价格时,将价格与时间戳加入两个堆中,并更新哈希表和最新时间戳。在获取最大和最小价格时,堆顶元素如果与哈希表中的当前价格不符,则将其移除,直到堆顶元素有效。最新价格直接通过最大时间戳在哈希表中查询获得。
时间复杂度:
O(log n)(对于update, maximum, 和 minimum操作)
空间复杂度:
O(n)
代码细节讲解
🦆
堆中可能会存在无效的股票价格,你是如何保证`maximum`和`minimum`方法中返回的价格是有效的?
▷🦆
你是如何处理堆中可能累积的无效元素的,会不会影响性能?
▷🦆
在确定最新股票价格时,你是如何确保`current`方法中返回的价格总是最新的?
▷🦆
为什么选择使用两个堆(一个最大堆和一个最小堆)来维护股票的价格,而不是使用其他数据结构?
▷