【每日一题Day341】LC2034股票价格波动 | 堆+哈希表

简介: 【每日一题Day341】LC2034股票价格波动 | 堆+哈希表

股票价格波动【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();
 */


目录
相关文章
|
7月前
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
54 0
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
|
7月前
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
55 0
|
7月前
|
存储
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
54 0
|
7月前
【每日一题Day340】LC2251花期内花的数目 | 差分+哈希表+排序 排序+二分查找
【每日一题Day340】LC2251花期内花的数目 | 差分+哈希表+排序 排序+二分查找
38 0
|
7月前
|
存储 人工智能 BI
【每日一题Day147】LC1615最大网络秩 | 枚举 哈希表
【每日一题Day147】LC1615最大网络秩 | 枚举 哈希表
54 0
|
7月前
|
存储
【每日一题Day123】LC1792最大平均通过率 | 堆
【每日一题Day123】LC1792最大平均通过率 | 堆
48 0
数据结构实验之栈与队列五:下一较大值(一)
数据结构实验之栈与队列五:下一较大值(一)
|
7月前
|
算法
[leetcode 哈希表] 2034. 股票价格波动 M
[leetcode 哈希表] 2034. 股票价格波动 M
|
7月前
【每日一题Day215】LC1090受标签影响的最大值 | 贪心+排序+哈希表
【每日一题Day215】LC1090受标签影响的最大值 | 贪心+排序+哈希表
46 0
|
7月前
【每日一题Day227】LC2465不同的平均值数目 | 排序 + 哈希表
【每日一题Day227】LC2465不同的平均值数目 | 排序 + 哈希表
31 0