stl运用题…
思路
这题麻烦就麻烦在更新后最大值最小值的维护问题。。。我也想到了用优先队列但是还是没做出来,,,然后看了别人题解发现好聪明。。。优先队列存一个PII,无论是更新旧的键值对还是插入新的键值对都往里面插入,查询最大最小值的时候只需要判断队列头部的键值对是否在map中,如果在就直接输出如果不在就弹出继续判断下一个队头…这个方法见代码1
代码2也挺厉害的…反正对stl容器的运用,建议好好研究研究
见: https://leetcode-cn.com/problems/stock-price-fluctuation/solution/liang-ge-you-xian-dui-lie-bu-zai-mapli-m-ju6s/
代码1
class StockPrice {
public:
typedef pair<int,int> PII;
priority_queue <PII> q1;//大根堆
priority_queue <PII,vector<PII>,greater<PII> >q2;//小根堆
map<int,int> mp;
StockPrice() {
}
void update(int timestamp, int price) {
mp[timestamp]=price;
q1.push({price,timestamp});
q2.push({price,timestamp});
}
int current() {
auto it=mp.end();
it--;
return it->second;
}
int maximum() {
auto it=q1.top();
while(mp[it.second]!=it.first)
{
q1.pop();
it=q1.top();
}
return q1.top().first;
}
int minimum() {
auto it=q2.top();
while(mp[it.second]!=it.first)
{
q2.pop();
it=q2.top();
}
return q2.top().first;
}
};
代码2
class StockPrice {
map<int,int> m;
set<pair<int,int>> s;
public:
StockPrice() {
m.clear();
s.clear();
}
void update(int timestamp, int price) {
if(m.count(timestamp))s.erase(make_pair(m[timestamp],timestamp));
s.insert(make_pair(m[timestamp]=price,timestamp));
}
int current() {
return m.rbegin()->second;
}
int maximum() {
return s.rbegin()->first;
}
int minimum() {
return s.begin()->first;
}
};