LeetCode-2034. Stock price fluctuation

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  .
 

Example 1：

Input ：
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Output ：
[null, null, null, 5, 10, null, 5, null, 2]

explain ：
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamp [1] , The corresponding stock price is [10] .
stockPrice.update(2, 5);  // Timestamp [1,2] , The corresponding stock price is [10,5] .
stockPrice.current();     // return 5 , The latest timestamp is 2 , The corresponding price is 5 .
stockPrice.maximum();     // return 10 , The timestamp of the highest price is 1 , The price for 10 .
stockPrice.update(1, 3);  // The previous timestamp was 1 Your price is wrong , Price updated to 3 .
                          // Timestamp [1,2] , The corresponding stock price is [3,5] .
stockPrice.maximum();     // return 5 , The corrected maximum price is 5 .
stockPrice.update(4, 2);  // Timestamp [1,2,4] , The corresponding price is [3,5,2] .
stockPrice.minimum();     // return 2 , The lowest price timestamp is 4 , The price for 2 .
 

Tips ：

1 <= timestamp, price <= 109
update,current,maximum  and  minimum  total The number of calls shall not exceed  105 .
current,maximum  and  minimum  When called ,update  operation At least   Has been called once  

Ideas ：

The stock price will be updated at any time , But each time we need to find an extreme value ,

Set up two priority queues , Calculate the maximum value respectively , minimum value , The purpose of the priority queue

It's order , The bottom layer is the data structure of large top heap or small top heap , Ensure that the data entering the queue every time is in order

The difficulties are 2 individual , One is storage stock Data structure to compare in the priority queue . Need to write their own imitation function comparison

The second is how to deal with stock updates , The fixed idea is to adjust the structure of the heap after changes have taken place

such as , Rearrange the heap , But let's think about it , That's inefficient , In fact, we only compare price, That's the price ,

As long as the correct time and price for each update are guaranteed , Take part in the comparison , We just need to get out of the team , Judge the maximum

Whether the minimum value is expired .

#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;


/*  Customize stock Stock structure  */
typedef struct Stock {
	int timestamp;
	int price;
}stock;

/*  Imitation function custom comparison method  */
class max_cmp {
public:
	bool operator () (const stock& x, const stock& y) {
		return (x.price < y.price);  // Big root pile 
	}
};

/*  Imitation function custom comparison method  */
class min_cmp {
public:
	bool operator () (const stock& x, const stock& y) {
		return (x.price > y.price);  // Heap 
	}
};

class StockPrice {
public:
	StockPrice() {
		cur_timestamp = INT_MIN;
	}

	void update(int timestamp, int price) {
		stock s;
		s.timestamp = timestamp;
		s.price = price;
		mp[timestamp] = price;
		cur_timestamp = max(cur_timestamp, timestamp);
		max_que.push(s);
		min_que.push(s);
	}


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

	/*  Delay deletion  */
	int maximum() {
		while (true) {
			int timestamp = max_que.top().timestamp;
			int price = max_que.top().price;
			/*  Only equality means , The stock structure has not expired  */
			if (mp[timestamp] == price) {
				return price;
			}
			max_que.pop();
		}
	}
	/*  Delay deletion  */
	int minimum() {
		while (true) {
			int timestamp = min_que.top().timestamp;
			int price = min_que.top().price;

			/*  Only equality means , The stock structure has not expired  */
			if (mp[timestamp] == price) {
				return price;
			}
			min_que.pop();
		}
	}

private:
	int cur_timestamp;
	unordered_map<int, int> mp;                                     /* key:timestamp, value:price */
	priority_queue<stock, vector<stock>, max_cmp> max_que;          /* max_que */
	priority_queue<stock, vector<stock>, min_cmp> min_que;          /* min_que */
};


/*  The following is the priority queue test method , It has nothing to do with the subject  */
int main() {

	Stock s1, s2, s3, s4;
	s1.timestamp = 1;
	s1.price = 10;

	s2.timestamp = 2;
	s2.price = 5;

	s3.timestamp = 3;
	s3.price = 8;

	s4.timestamp = 4;
	s4.price = 7;

	priority_queue<stock, vector<stock>, max_cmp> max_que;          /* max_que */
	priority_queue<stock, vector<stock>, min_cmp> min_que;          /* min_que */

	min_que.push(s1);
	min_que.push(s2);
	min_que.push(s3);
	min_que.push(s4);

	while (!min_que.empty()) {
		stock s = min_que.top();
		cout << "time:" << s.timestamp << endl;
		cout << "price:" << s.price << endl;
		min_que.pop();
	}

	system("pause");
	return 0;
}