这两道题都是单调栈专题中的引子题目,
如果我们仔细分析题目,如果只是想得到当前历史数据中最小值和可以发现这两道题,
都不用使用一个额外的容器装以往所有的历史数据才能得到结果
对于155来说,
只需要维护最小栈就可以快速获得当前的最小元素,而不用通过遍历所有历史数据才能获得最小元素
首先,如果插入了一个大于最小栈栈顶的元素val,之后无论怎么操作,这个val都不可能成为最小元素,为了解释这一点,我们可以进行分析:
case1: val比栈中所有历史插入数据都小,
case2: val和栈中所有历史插入数据中的最小值一样大
case3: val至少比历史插入数据中的一个数据大
那么如果插入了一个大于最小栈栈顶的元素val,就只能是case3
那么之后如果插入数据都比val大,之前在栈中还是会有小于val的数据,那么之后查询最小值一定不是val
如果不断pop数据,val自然也会被首先pop掉,之后插入的任何值的大小和val本身无关
class MinStack {stack<pair<int, int>> _strecord;
public:MinStack() {_strecord.emplace(make_pair(0, INT_MAX));}void push(int val) {if(val < _strecord.top().second){_strecord.emplace(make_pair(val, val));}else{_strecord.emplace(make_pair(val, _strecord.top().second));}}void pop() {_strecord.pop();}int top() {return _strecord.top().first;}int getMin() {return _strecord.top().second;}
};
对于901来说,这个题要求必须是小于或等于今天价格的最大连续日数
所以从当天往回数,一旦遇到一个比当天价格更高的一天,就立刻停止往前数,那么是否还有必要保存以往的历史价格呢?答案是没必要,只需要知道离当前最近的连续价格下降的那些日子的价格即可,这可以用一个单调栈来保存这些价格
class StockSpanner {
stack<pair<int, int>> decpri_span;
public:StockSpanner() {}int next(int price) {int ret = 1;while(!decpri_span.empty() && decpri_span.top().first <= price){ret += decpri_span.top().second;decpri_span.pop();}decpri_span.emplace(make_pair(price, ret));return ret;}
};