股票价格波动【LC2034】
给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。
不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。
请你设计一个算法，实现：
更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
找到当前记录里股票的 最高价格 。
找到当前记录里股票的 最低价格 。
请你实现 StockPrice 类：
StockPrice() 初始化对象，当前无股票价格记录。
void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
int current() 返回股票 最新价格 。
int maximum() 返回股票 最高价格 。
int minimum() 返回股票 最低价格 。
放假回家 电脑坏了 国庆休息的好舒服 继续打卡
思路
使用哈希表存储每个时间点对应的价格，并使用小顶堆和大顶堆记录二元组[ 时间，价格 ] [时间，价格][时间，价格]，以价格进行排序，同时记录最大时间点maxTime
update：将数据记录在哈希表、小顶堆、大顶堆，并判断是否需要更新最大时间点maxTime
current：从哈希表中获得maxTime对应的价格
maximum/minimum：如果一个时间点的价格与哈希表中不一致，那么不是有效数据，将大顶堆/小顶堆中的无效数据移除后，返回堆顶元素
实现
class StockPrice { // 如果发生了价格更正，那么会影响最高价格和最低价格 // 使用小顶堆、大顶堆存放二元组[时间，价格]，哈希表记录每个时间对应的最新价格 堆顶元素时间对应的价格必须与哈希表一致 // 记录最大时间 PriorityQueue<int[]> mxPq; PriorityQueue<int[]> mnPq; int mxTime; Map<Integer,Integer> map; public StockPrice() { this.mxPq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]); this.mnPq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); mxTime = -1; map = new HashMap<>(); } public void update(int timestamp, int price) { map.put(timestamp, price); mxTime = Math.max(mxTime, timestamp); mxPq.add(new int[]{timestamp, price}); mnPq.add(new int[]{timestamp, price}); } public int current() { return map.get(mxTime); } public int maximum() { // 懒删除 while (mxPq.peek()[1] != map.get(mxPq.peek()[0])){ mxPq.poll(); } return mxPq.peek()[1]; } public int minimum() { // 懒删除 while (mnPq.peek()[1] != map.get(mnPq.peek()[0])){ mnPq.poll(); } return mnPq.peek()[1]; } } /** * 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(); */
