2034. 股票价格波动

2034.股票价格波动

题目描述：

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

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

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

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

请你实现 StockPrice 类：

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

数据范围：

$1\le ts, price \le 10^9$

总调用次数不超过 $10^5$ 。

题解：

之前在顶点覆盖的顶点贪心算法中使用过。之前是由于后面遇到的都是对当前值改小的操作，因此取最大值的时候，就不用把修改的插入堆了。上次是看弹出的，如果是旧结果那么就修改，重新push回去。

但是这里不能用，因为如果是改大的，那么可能原值比较小，最大堆弹出的是比原值大的，而且不是旧值，那么就会出现错误，当前最大值应该是原值对应的新值。

因此在修改时，直接把修改后的新值也放入堆中，然后每次从堆中弹出时，看是否是旧值，如果是旧值，就继续弹。

也可以使用另一种方法，记录 $price$ 出现的次数，每次修改时，将 $price$ 次数减减，如果为 $0$ 则删除。这样的话只需要求已存在的 $price$ 最大值最小值即可。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class StockPrice
{
public:
    unordered_map<int, int> mp; // time, price
    int last_time;
    priority_queue<pair<int, int>> maxq;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minq;
    StockPrice()
    {
        last_time = -1;
    }

    void update(int timestamp, int price)
    {
        maxq.push({price, timestamp});
        minq.push({price, timestamp});
        mp[timestamp] = price;
        if (timestamp > last_time)
            last_time = timestamp;
    }

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

    int maximum()
    {
        while (maxq.size() && mp[maxq.top().second] != maxq.top().first)
        {
            maxq.pop();
        }
        return maxq.top().first;
    }

    int minimum()
    {
        while (minq.size() && mp[minq.top().second] != minq.top().first)
        {
            minq.pop();
        }
        return minq.top().first;
    }
};