Stock Price Fluctuation
Advertisement
Problem
StockPrice: update(timestamp, price), current(), maximum(), minimum(). Prices can be corrected (same timestamp updated).
Key insight: Map timestamp→price + sorted multiset (or two heaps with lazy deletion) for max/min.
Solutions
# Python
from sortedcontainers import SortedList
class StockPrice:
def __init__(self):
self.prices = {}
self.sorted = SortedList()
self.max_ts = 0
def update(self, timestamp, price):
if timestamp in self.prices:
self.sorted.remove(self.prices[timestamp])
self.prices[timestamp] = price
self.sorted.add(price)
self.max_ts = max(self.max_ts, timestamp)
def current(self):
return self.prices[self.max_ts]
def maximum(self):
return self.sorted[-1]
def minimum(self):
return self.sorted[0]
// C++
class StockPrice {
map<int,int> ts_price;
multiset<int> prices;
int maxTs = 0;
public:
void update(int ts, int price) {
if(ts_price.count(ts)) prices.erase(prices.find(ts_price[ts]));
ts_price[ts]=price; prices.insert(price);
maxTs=max(maxTs,ts);
}
int current(){return ts_price[maxTs];}
int maximum(){return *prices.rbegin();}
int minimum(){return *prices.begin();}
};
// Java
class StockPrice {
Map<Integer,Integer> tsPrice=new HashMap<>();
TreeMap<Integer,Integer> priceCnt=new TreeMap<>();
int maxTs=0;
public void update(int ts, int price) {
if(tsPrice.containsKey(ts)){int old=tsPrice.get(ts);priceCnt.merge(old,-1,Integer::sum);if(priceCnt.get(old)==0)priceCnt.remove(old);}
tsPrice.put(ts,price); priceCnt.merge(price,1,Integer::sum); maxTs=Math.max(maxTs,ts);
}
public int current(){return tsPrice.get(maxTs);}
public int maximum(){return priceCnt.lastKey();}
public int minimum(){return priceCnt.firstKey();}
}
// JavaScript
class StockPrice {
constructor(){this.prices={};this.sorted=[];this.maxTs=0;}
update(ts,price){
if(ts in this.prices){const old=this.prices[ts];const i=this.sorted.indexOf(old);if(i>=0)this.sorted.splice(i,1);}
this.prices[ts]=price;
let p=this.sorted.findIndex(x=>x>=price);
if(p===-1)this.sorted.push(price);else this.sorted.splice(p,0,price);
if(ts>this.maxTs)this.maxTs=ts;
}
current(){return this.prices[this.maxTs];}
maximum(){return this.sorted[this.sorted.length-1];}
minimum(){return this.sorted[0];}
}
Complexity
- update: O(log n), min/max/current: O(1)
Advertisement
← Previous
Reduce Array Size to At Least HalfNext →
Seat Reservation Manager