2034. 股票价格波动
难度: 中等
来源: 每日一题 2023.10.08
给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。
不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。
请你设计一个算法，实现：
-
更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
-
找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
-
找到当前记录里股票的 最高价格 。
-
找到当前记录里股票的 最低价格 。
请你实现 StockPrice 类：
StockPrice()初始化对象，当前无股票价格记录。void update(int timestamp, int price)在时间点timestamp更新股票价格为price。int current()返回股票 最新价格 。int maximum()返回股票 最高价格 。int minimum()返回股票 最低价格 。
示例 1：
输入：
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
输出：
[null, null, null, 5, 10, null, 5, null, 2]
解释：
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // 时间戳为 [1] ，对应的股票价格为 [10] 。
stockPrice.update(2, 5); // 时间戳为 [1,2] ，对应的股票价格为 [10,5] 。
stockPrice.current(); // 返回 5 ，最新时间戳为 2 ，对应价格为 5 。
stockPrice.maximum(); // 返回 10 ，最高价格的时间戳为 1 ，价格为 10 。
stockPrice.update(1, 3); // 之前时间戳为 1 的价格错误，价格更新为 3 。
// 时间戳为 [1,2] ，对应股票价格为 [3,5] 。
stockPrice.maximum(); // 返回 5 ，更正后最高价格为 5 。
stockPrice.update(4, 2); // 时间戳为 [1,2,4] ，对应价格为 [3,5,2] 。
stockPrice.minimum(); // 返回 2 ，最低价格时间戳为 4 ，价格为 2 。
提示：
1 <= timestamp, price <= 10^9update，current，maximum和minimum总 调用次数不超过10^5。current，maximum和minimum被调用时，update操作 至少 已经被调用过 一次 。
class StockPrice {
public StockPrice() {
}
public void update(int timestamp, int price) {
}
public int current() {
}
public int maximum() {
}
public int minimum() {
}
}
/**
* 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();
*/
分析与题解
-
HashMap缓存 (时间超时 失败)
自己尝试做这个题目, 我当时的思路是这样的.
-
最新股票价格的思路是我不能存储一个最新价格A, 只存储最新价格A会导致 更正操作 来临时, 你不知道是否要更新最新股票价格. 所以解决方案是应该存储时间戳, 通过时间戳来获取最新价格.if (currentPriceTime < timestamp) { currentPriceTime = timestamp; } -
最高价格与最低价格在普通更新操作中比较简单, 我们只需要判断当前更新的价格与最高价格最低价格两者的关系进而更新即可.if(price < minPrice) { minPrice = price; } if(price > maxPrice) { maxPrice = price; } -
最高价格与最低价格在 更正操作 中, 我们需要判断在更新完成, 从价格HashMap中(PS: 存储了所有的价格)重新获取最高价格与最低价格.if(needUpdatePrice == maxPrice || needUpdatePrice == minPrice) { int maxPriceNow = Integer.MIN_VALUE; int minPriceNow = Integer.MAX_VALUE; for(Integer key : cache.keySet()) { if(cache.get(key) < minPriceNow) { minPriceNow = cache.get(key); } if(cache.get(key) > maxPriceNow) { maxPriceNow = cache.get(key); } } maxPrice = maxPriceNow; minPrice = minPriceNow; }
我们一起看一下当时的解题过程.
class StockPrice { Map<Integer, Integer> cache = new HashMap<>(); int maxPrice = Integer.MIN_VALUE; int minPrice = Integer.MAX_VALUE; int currentPriceTime = 0; public StockPrice() { } public void update(int timestamp, int price) { if(price < minPrice) { minPrice = price; } if(price > maxPrice) { maxPrice = price; } if(cache.get(timestamp) == null) { if (currentPriceTime < timestamp) { currentPriceTime = timestamp; } cache.put(timestamp, price); } else { int needUpdatePrice = cache.get(timestamp); cache.put(timestamp, price); if(needUpdatePrice == maxPrice || needUpdatePrice == minPrice) { int maxPriceNow = Integer.MIN_VALUE; int minPriceNow = Integer.MAX_VALUE; for(Integer key : cache.keySet()) { if(cache.get(key) < minPriceNow) { minPriceNow = cache.get(key); } if(cache.get(key) > maxPriceNow) { maxPriceNow = cache.get(key); } } maxPrice = maxPriceNow; minPrice = minPriceNow; } } } public int current() { return cache.get(currentPriceTime); } public int maximum() { return maxPrice; } public int minimum() { return minPrice; } } /** * 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(); */复杂度分析:
- 时间复杂度: O(n), 更正操作中需要遍历整个
cache - 空间复杂度: O(2n),
cache空间复杂度都与元素个数长度相关.
结果如下所示.
-
-
HashMap缓存 + 有序集合
在先前的思路中, 如果使用
HashMap缓存对于操作层面来说, 有一个操作会非常的耗时, 那就是 更新操作, 更新操作之后对于最大价格,最小价格都可能会造成影响.所以在
HashMap缓存的思想中, 我们只能遍历价格的Map, 找到最大价格和最少价格. 从而导致超时失败.那么, 官方如何解决这个问题的呢? 官方是利用 TreeMap 的
自动排序特性, 从而减少遍历过程的时间复杂度.对于 TreeMap, 其中 key为价格, value为价格的天数(PS: 哪些天处于key价格)
具体来说, 当触发更新操作 (PS: 判断
timestamp的时间点的价格是否存在) 之后, 更新其中的天数即可, 如果天数为0, 那么就移除即可.int prevPrice = cache.getOrDefault(timestamp, 0); if(prevPrice > 0) { prices.put(prevPrice, prices.get(prevPrice) - 1); if(prices.get(prevPrice) == 0) { prices.remove(prevPrice); } }不管是新增还是更新, 我们要同时更新
HashMap和TreeMap中的数据.cache.put(timestamp, price); ... prices.put(price, prices.getOrDefault(price, 0) + 1);对于当前价格, 我们只需要存储最后的日期, 每一次更新操作, 我们都尝试更新这个最后日期.
currentPriceTime = Math.max(currentPriceTime, timestamp);所以, 我们获取最新价格就很简单了, 直接根据
currentPriceTime去cache取值即可.public int current() { return cache.get(currentPriceTime); }对于最大值和最小值来说, 我们直接从 TreeMap 取
lastKey和firstKey即可.public int maximum() { return prices.lastKey(); } public int minimum() { return prices.firstKey(); }至此所有的逻辑就完成了, 我们一起看一下整体的解题过程.
class StockPrice { Map<Integer, Integer> cache = new HashMap<>(); TreeMap<Integer, Integer> prices = new TreeMap<>(); int currentPriceTime = 0; public StockPrice() { } public void update(int timestamp, int price) { currentPriceTime = Math.max(currentPriceTime, timestamp); int prevPrice = cache.getOrDefault(timestamp, 0); cache.put(timestamp, price); if(prevPrice > 0) { prices.put(prevPrice, prices.get(prevPrice) - 1); if(prices.get(prevPrice) == 0) { prices.remove(prevPrice); } } prices.put(price, prices.getOrDefault(price, 0) + 1); } public int current() { return cache.get(currentPriceTime); } public int maximum() { return prices.lastKey(); } public int minimum() { return prices.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(); */
复杂度分析:
- 时间复杂度: O(1), 每一个操作时间复杂度都是常量级别的
- 空间复杂度: O(2n),
cache和prices空间复杂度都与元素个数长度相关.
结果如下所示.
Comments | 0 条评论