- 每日一题：LeetCode：2034.股票价格波动
- 时间：2022-01-23
- 力扣难度：Medium
- 个人难度：Medium-
- 数据结构：数组、哈希表、有序集合
2022-01-23：LeetCode：2034.股票价格波动
1. 题目描述
题目：原题链接
- 给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的价格 。
- 不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。
- 某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录更正前一条错误的记录。
- 请你设计一个算法，实现：
- 更新股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将更正之前的错误价格。
- 找到当前记录里最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
- 找到当前记录里股票的最高价格 。
- 找到当前记录里股票的最低价格 。
- 请你实现 StockPrice 类：
StockPrice()初始化对象，当前无股票价格记录。void update(int timestamp, int price)在时间点 timestamp 更新股票价格为 price 。int current()返回股票 最新价格 。int maximum()返回股票 最高价格 。int minimum()返回股票 最低价格 。
1 <= timestamp, price <= 10^9- update，current，maximum 和 minimum 总 调用次数不超过 10^5 。
- current，maximum 和 minimum 被调用时，update 操作 至少 已经被调用过 一次 。
2. 方法：哈希表 & 有序集合
思路
本题为设计题，针对各个功能逐一分析实现
更新价格：通过时间戳更新价格，可以使用哈希表来存储时间戳-价格 K-V 对，然后添加元素时，判断key时间戳是否相同，更新相同时间戳的value价格
最新价格
- 既可以排序来找到最大时间戳，也可以通过维护一个大顶堆，堆顶元素就是最大时间戳，然后通过最大时间戳去哈希表中查询价格即可
- 使用排序要额外话线性对数级时间复杂度，而使用大顶堆也需要线性额外空间，我们可以只使用一个变量来记录最大时间戳，在进行更新操作时同步更新该值
最大、最小价格：有序集合
- 通过有序集合，如TreeMap来存放价格-个数 K-V 对，因为有序集合可以实现自然排序或者定制排序，就可以得到最大最小值
- 要注意的是，每次进行更新操作的同时，需要对有序集合同步更新，即如果一个价格被替换了，那么有序集合中该价格的个数要减一，如果个数为0了，表示该价格不存在，需要移除该元素
最大、最小价格：堆、优先队列
- 使用有序集合，是在更新操作中删除有序集合中过期的价格，如果大量调用更新操作的话，相对而言效率不高
- 所以也可以在获取最大最小值的时候才进行过期价格的删除，类似Redis的惰性删除，即延迟删除
- 此时，通过两个堆来存放价格，一个是大顶堆、一个是小顶堆，分别对应最大最小价格，因为此时需要判断价格是否过期，所以堆中存储的是价格和时间戳，通过时间戳在哈希表中查询价格，判断价格是否一致来判断是否过期
- 如果已经过期，就将堆顶的元素移除，然后判断新的堆顶元素，直到不过期位置
题解：哈希表 & 有序集合 TreeMap
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
37public class StockPrice {
int maxTimeStamp;
Map<Integer, Integer> timeStampMap;
TreeMap<Integer, Integer> priceMap;
public StockPrice() {
maxTimeStamp = 0;
timeStampMap = new HashMap<>();
priceMap = new TreeMap<>();
}
public void update(int timestamp, int price) {
maxTimeStamp = Math.max(maxTimeStamp, timestamp);
int oldPrice = timeStampMap.getOrDefault(timestamp, -1);
timeStampMap.put(timestamp, price);
// 更新 TreeMap
if (oldPrice != -1) {
priceMap.put(oldPrice, priceMap.get(oldPrice) - 1);
if (priceMap.get(oldPrice) == 0) priceMap.remove(oldPrice);
}
priceMap.put(price, priceMap.getOrDefault(price, 0) + 1);
}
public int current() {
return timeStampMap.get(maxTimeStamp);
}
public int maximum() {
return priceMap.lastKey();
}
public int minimum() {
return priceMap.firstKey();
}
}
题解：哈希表 & 堆
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
45class StockPrice {
int maxTimeStamp;
Map<Integer, Integer> timeStampMap;
PriorityQueue<int[]> maxDeap;
PriorityQueue<int[]> minDeap;
public StockPrice() {
maxTimeStamp = 0;
timeStampMap = new HashMap<>();
minDeap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
maxDeap = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
}
public void update(int timestamp, int price) {
maxTimeStamp = Math.max(maxTimeStamp, timestamp);
timeStampMap.put(timestamp, price);
maxDeap.add(new int[]{price, timestamp});
minDeap.add(new int[]{price, timestamp});
}
public int current() {
return timeStampMap.get(maxTimeStamp);
}
public int maximum() {
while (!maxDeap.isEmpty()) {
int price = maxDeap.peek()[0];
int timeStamp = maxDeap.peek()[1];
if(timeStampMap.get(timeStamp) == price) return price;
maxDeap.poll();
}
return -1;
}
public int minimum() {
while (!minDeap.isEmpty()) {
int price = minDeap.peek()[0];
int timeStamp = minDeap.peek()[1];
if(timeStampMap.get(timeStamp) == price) return price;
minDeap.poll();
}
return -1;
}
}复杂度分析：n 是更新操作的次数，复杂度依赖使用的数据结构
- 时间复杂度
- 构造方法：$O(1)$
- update()：$O(logn)$，因为更新了TreeMap或将元素添加到了优先队列，此时会排序
- current()：$O(1)$
- maximum()、minimum()：$O(logn)$，对于TreeMap，查询最大值最小值是二分对数级；对于优先队列，虽然查询是常数级，但是因为还要判断价格是否过期，平均下来约为对数级
- 空间复杂度：$O(n)$
- 时间复杂度
本文作者：
Chthollists
发布时间： 2022-01-23 14:41:53
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2034.股票价格波动
本文链接： https://chthollists.github.io/post/c848403e.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2022-01-23 14:41:53
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2034.股票价格波动
本文链接： https://chthollists.github.io/post/c848403e.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
