当前位置:网站首页>LeetCode-2034. Stock price fluctuation
LeetCode-2034. Stock price fluctuation
2022-06-12 06:23:00 【Border wanderer】
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;
}
边栏推荐
- The vs 2019 community version Microsoft account cannot be logged in and activated offline
- PHP 开发环境搭建及数据库增删改查
- Mastering UI development with unity
- Logistic regression model
- Highlight detection with pairwise deep ranking for first person video summary (thesis translation)
- RMB classification II
- Sqlite Cross - compile Dynamic Library
- In unity3d, billboard effect can be realized towards another target
- 相机图像质量概述
- Redis application (I) -- distributed lock
猜你喜欢

Pytorch implementation of regression model

dlib 人脸检测

Leetcode-1535. Find the winner of the array game

Overview of camera image quality

AI operation ch8

Chartextcnn (Ag dataset - news topic classification)

Jetson TX2 machine brushing jetpack4.2 (self test successful version)

Explanation of sensor flicker/banding phenomenon

Redis configuration (III) -- master-slave replication

. Net core - pass Net core will Net to cross platform
随机推荐
Word vector training based on nnlm
Directx11 advanced tutorial PBR (1) summary of physical phenomena of light
Leetcode-1705. Maximum number of apples to eat
SQLite cross compile dynamic library
(UE4 4.27) customize primitivecomponent
2D human pose estimation for pose estimation - pifpaf:composite fields for human pose estimation
(UE4 4.27) add globalshder to the plug-in
Redis configuration (III) -- master-slave replication
Redis data structure (VIII) -- Geo
Leetcode personal question solution (Sword finger offer3-5) 3 Duplicate number in array, 4 Find in 2D array, 5 Replace spaces
Multithreading mode (I) -- protective pause and join source code
PDF. JS help file
Textcnn (MR dataset - emotion classification)
Mastering UI development with unity
Pytorch implementation of regression model
Multithreading (IV) -- no lock (IV) -- unsafe
C # converts the hexadecimal code form of text to text (ASCII)
Guns framework multi data source configuration without modifying the configuration file
SQL注入——联合查询union
leetcode 278. First wrong version