2021.10.10 deduction - stock price fluctuation

It's too powerful 2022-01-15 01:45:57

Title Description :

Give you a data stream of stock prices . Each record in the data flow contains a Time stamp   Corresponding to the stock at this time point Price  .

unfortunately , Due to the inherent volatility of the stock market , Stock price records may not come in chronological order . In some cases , Some records may be wrong . If two records with the same timestamp appear in the data stream , The previous record is regarded as an error record , Records that appear after correct   The previous wrong record .

Please design an algorithm , Realization :

to update The price of a stock at a certain time stamp , If there is a previous price with the same timestamp , This operation will   correct   Previous wrong price .
Find the current record The latest stock price  . The latest stock price   Defined as the stock price with the latest timestamp .
Find the stock in the current record The highest price  .
Find the stock in the current record The lowest price  .
Please realize  StockPrice  class :

StockPrice()  Initialize object , There is no stock price record at present .
void update(int timestamp, int price)  At time timestamp  Update the stock price to price .
int current()  Return stock The latest price  .
int maximum()  Return stock The highest price  .
int minimum()  Return stock The lowest price  .

Method 1 :

class StockPrice {
public:
unordered_map<int, int> maps; // Store the price corresponding to a timestamp
int latesttime = INT_MIN; // Record the latest time
// The first element of the priority queue is price , The second element is time
// In descending and ascending price order respectively
priority_queue<pair<int, int>> maxpriceque;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minpriceque;
StockPrice() {
}
void update(int timestamp, int price) {
latesttime = max(latesttime, timestamp);
maps[timestamp] = price;
maxpriceque.push(pair<int, int>(price, timestamp));
minpriceque.push(pair<int, int>(price, timestamp));
}
int current() {
return maps[latesttime];
}
int maximum() {
// The former is maxpriceque The time corresponding to the first element of ,maps The price in (maps The price in must be the last updated )
// The latter is maxpriceque The price corresponding to the first element of
// If the two are not equal , explain maxpriceque The first element of is a previous error record , It should be deleted
while (maps[maxpriceque.top().second] != maxpriceque.top().first)
{
maxpriceque.pop();
}
return maxpriceque.top().first;
}
int minimum() {
// The former is minpriceque The time corresponding to the first element of ,maps The price in (maps The price in must be the last updated )
// The latter is minpriceque The price corresponding to the first element of
// If the two are not equal , explain minpriceque The first element of is a previous error record , It should be deleted
while (maps[minpriceque.top().second] != minpriceque.top().first)
{
minpriceque.pop();
}
return minpriceque.top().first;
}
};

Another day to look at the solution ~

The idea is right , It is realized by using hash table and priority queue , But I don't know when updating the price of a time stamp , How to delete the original record in the priority queue , Looked at other people's methods , The elements in the priority queue are used pair, And pair The first element of is price , The second element is time !

It feels so wonderful , Seek the highest in the follow-up 、 At the lowest price , Each price stored in the queue has a corresponding time , because maps What is stored in the must be the right price , So as long as we judge whether the price corresponding to the time in the priority queue is correct, we can determine whether it is an error record that can be deleted !


thank
Similar articles
***

2022-01-15

***

2022-01-15

***

2022-01-15

2022-01-15

2022-01-15

2022-01-15

2022-01-15

2022-01-15