leetcode5896. 股票價格波動 (hash表 multiset 設計類)

​

題目

給你一支股票價格的資料流。資料流中每一條記錄包含一個 時間戳 和該時間點股票對應的 價格 。

不巧的是，由于股票市場内在的波動性，股票價格記錄可能不是按時間順序到來的。某些情況下，有的記錄可能是錯的。如果兩個有相同時間戳的記錄出現在資料流中，前一條記錄視為錯誤記錄，後出現的記錄 更正 前一條錯誤的記錄。

請你設計一個算法，實作：

更新 股票在某一時間戳的股票價格，如果有之前同一時間戳的價格，這一操作将 更正 之前的錯誤價格。

找到目前記錄裡 最新股票價格 。最新股票價格 定義為時間戳最晚的股票價格。

找到目前記錄裡股票的 最高價格 。

找到目前記錄裡股票的 最低價格 。

請你實作 StockPrice 類：

StockPrice() 初始化對象，目前無股票價格記錄。

void update(int timestamp, int price) 在時間點 timestamp 更新股票價格為 price 。

int current() 傳回股票 最新價格 。

int maximum() 傳回股票 最高價格 。

int minimum() 傳回股票 最低價格 。

用例

示例 1：

輸入：

["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]

[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]

輸出：

[null, null, null, 5, 10, null, 5, null, 2]

解釋：

StockPrice stockPrice = new StockPrice();

stockPrice.update(1, 10); // 時間戳為 [1] ，對應的股票價格為 [10] 。

stockPrice.update(2, 5); // 時間戳為 [1,2] ，對應的股票價格為 [10,5] 。

stockPrice.current(); // 傳回 5 ，最新時間戳為 2 ，對應價格為 5 。

stockPrice.maximum(); // 傳回 10 ，最高價格的時間戳為 1 ，價格為 10 。

stockPrice.update(1, 3); // 之前時間戳為 1 的價格錯誤，價格更新為 3 。

// 時間戳為 [1,2] ，對應股票價格為 [3,5] 。

stockPrice.maximum(); // 傳回 5 ，更正後最高價格為 5 。

stockPrice.update(4, 2); // 時間戳為 [1,2,4] ，對應價格為 [3,5,2] 。

stockPrice.minimum(); // 傳回 2 ，最低價格時間戳為 4 ，價格為 2 。

提示：

1 <= timestamp, price <= 109

update，current，maximum 和 minimum 總 調用次數不超過 105 。

current，maximum 和 minimum 被調用時，update 操作 至少 已經被調用過 一次 。

思路

周賽第三題

在更新股票價格情況下 維護最大最小值情況下 由于對stl中容器使用不太熟悉

在每次更新錯誤價格的情況下 對存儲數組排序 取最大最小值

很不幸逾時

class StockPrice {
public:
    StockPrice() {

    }

    void update(int timestamp, int price) {
        int ischange=0;
        int temp=0;
        if(mp.find(timestamp)!=mp.end())
        {
            ischange=1;
            temp=mp[timestamp];
        }
        mp[timestamp]=price;
        if(!ischange){
            if(price>maxnum)
                maxnum=price;
            if(price<minnum)
                minnum=price;
        }
        else{
            if(minnum==temp||maxnum==temp)
            {
                maxnum=INT_MIN;
                minnum=INT_MAX;
                for(auto it=mp.begin();it!=mp.end();it++)
                {
                    int t=it->second;
                    if(t>maxnum)
                        maxnum=t;
                    if(t<minnum)
                        minnum=t;
                }
            }else{
            if(price>maxnum)
                maxnum=price;
            if(price<minnum)
                minnum=price;
            }
        }
        if(timestamp>last)
            last=timestamp;

    }

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

    int maximum() {
        return maxnum;
    }

    int minimum() {
        return minnum;

    }
private:
    int maxnum=INT_MIN;
    int minnum=INT_MAX;
    unordered_map<int,int>mp;
    int last=0;


};
      

實際上維護一個有序容器 隻需用到stl中的multiset 自動排序 并且允許重複

在更新錯誤資料時 先将multiset中原資料時間戳對應的價格删去 注意不能直接erase目标值，會導緻所有與目标值相等的元素都被删除 應該選擇删除multiset中第一次與目标值相等的疊代器指向的元素 即​

​ms.erase(ms.find(mp[timestamp]));​

class StockPrice {
public:
    StockPrice() {
    }

    void update(int timestamp, int price) {
        if(mp.find(timestamp)!=mp.end())
        {
            ms.erase(ms.find(mp[timestamp]));
        }
        mp[timestamp]=price;
        ms.insert(price);
        if(timestamp>last)
            last=timestamp;
    }

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

    int maximum() {
        return *ms.rbegin();
    }

    int minimum() {
        return *ms.begin();
    }
private:
    unordered_map<int,int>mp;
    multiset<int>ms;
    int last=0;
};