[数据结构与算法]LeetCode 2034:股票价格波动

LeetCode 2034:股票价格波动

原题地址

基本思路

本题的难点在于不同数据结构的配合使用，这里同时使用了哈希表和有序集合。容易想到用哈希表来保存<时间戳，价格>关系，所以用到了C++的unordered_map（注意不能用基于红黑树的map，map的查询效率是对数级，而unordered_map则是常数级）。
只用哈希表存在的问题是，当已存在的时间点被更新时，重新获取最大最小元素需要扫描整个哈希表，代价太大。所以需要一个有序集合来保存所有哈希表中的价格，因此用到了multiset。
更新数据
哈希表部分，直接更新时间戳的价格或插入键值对；
有序集合部分，若时间戳已存在，则删除有序集合中的一个价格元素。接着将新价格插入有序集合中。

代码

class StockPrice {
public:
    StockPrice() {
        lastTS=0;
    }
    
    void update(int timestamp, int price) {
        lastTS=std::max(timestamp,lastTS);

        int prePrice = mp.count(timestamp)? mp[timestamp]: 0;
        mp[timestamp] = price;
        if(prePrice > 0)
        {
            auto it = p.find(prePrice);
            if(it!=p.end())
            {
                p.erase(it);
            }
        }
        p.emplace(price);
    }
    
    int current() {
        return mp[lastTS];
    }
    
    int maximum() {
        return *p.rbegin();
    }
    
    int minimum() {
        return *p.begin();
    }

    int lastTS;

    std::unordered_map<int ,int> mp;
    std::multiset<int> p;
};