题目

给你一支股票价格的数据流。数据流中每一条记录包含一个时间戳和该时间点股票对应的价格。

不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录更正前一条错误的记录。

请你设计一个算法，实现：

更新股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将更正之前的错误价格。
找到当前记录里最新股票价格。最新股票价格定义为时间戳最晚的股票价格。
找到当前记录里股票的最高价格。
找到当前记录里股票的最低价格。

请你实现 StockPrice 类：

StockPrice() 初始化对象，当前无股票价格记录。
void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
int current() 返回股票最新价格。
int maximum() 返回股票最高价格。
int minimum() 返回股票最低价格。

来源：力扣（LeetCode）

解答

要建立的类，需要有一个存入数据的方法，和三个返回数据的方法。

由于返回数据包含最新价格、最高价格和最低价格，所以考虑使用堆来存储价格，同时一个变量来存储最新时间戳，再通过一个哈希表来建立时间-价格映射。

哈希表，用来建立所有时间-价格映射；
最新时间，即用来返回current的价格；
大根堆，将所有价格存储到堆，用来保证取最高价格；
小根堆，同上，用来取最低价格。

此时，需要解决一个问题，就是有update的问题，即可能对已有数据进行修改，而堆的结构特性使得已有时间戳的数据不易修改，因此可以通过延缓处理的方式来解决：

一方面，堆存储的基本单位为{price, timeStamp}，而不仅仅是price；
另一方面，当出现数据修正时，直接将新的{price, timeStamp}入堆，同时更改哈希表的映射即可。
当需要返回最高价格时，通过取大根堆的顶来获得，但是需要进行一个判定，即取出的堆顶元素是否有效（有效：通过堆顶timeStamp查询哈希表的price，与堆顶取的price进行一致性判定，一致则为有效，否则无效），无效则将堆顶pop，并重新取顶，直至有效；
最低价格同理。

代码如下：

class StockPrice {
private:
    unordered_map<int, int> mp;

    int curTimeStamp;

    // 大根堆
    priority_queue<pair<int, int>, vector<pair<int, int>>> maxPq;

    // 小根堆
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minPq;

public:
    StockPrice() {

    }

    void update(int timestamp, int price) {
        // 最大时间戳更新
        if (timestamp > curTimeStamp) {
            curTimeStamp = timestamp;
        }

        // 哈希映射
        // 如果已有该时间，则修正为新的价格，否则直接添加
        mp[timestamp] = price;

        // 入堆
        maxPq.push({price, timestamp});
        minPq.push({price, timestamp});
    }

    int current() {
        return mp[curTimeStamp];
    }

    int maximum() {
        // 利用大根堆
        while (true) {
            auto get = maxPq.top();
            // 查询哈希表，是否已经进行了更改
            if (mp[get.second] != get.first) {
                maxPq.pop();
                continue;
            }

            return get.first;
        }
    }

    int minimum() {
        // 利用小根堆
        while (true) {
            auto get = minPq.top();
            // 查询哈希表，是否已经进行了更改
            if (mp[get.second] != get.first) {
                minPq.pop();
                continue;
            }

            return get.first;
        }
    }
};

2034. 股票价格波动

题目

解答