題目描述
定義棧的數(shù)據(jù)結構壹士，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復雜度應為O（1））尘吗。
注意：保證測試中不會當棧為空的時候钾埂，對棧調(diào)用pop()或者min()或者top()方法鳖枕。
思路1：
第一想法是添加一個變量min保存當前最小元素庄敛，每次入棧的時候更新min的值闰集，但是出棧的時候對最小值的更新就比較麻煩了沽讹，如果當前出棧元素就是最小值，那么怎么找到次小元素更新min值呢武鲁？
因此需要借助一個輔助棧爽雄，也就是最小元素棧。 每次壓棧操作時, 如果壓棧元素比當前最小元素更小, 就把這個元素壓入最小元素棧, 原本的最小元素就成了次小元素.沐鼠。同理, 彈棧時, 如果彈出的元素和最小元素棧的棧頂元素相等, 就把最小元素的棧頂彈出挚瘟。
代碼實現(xiàn)：
class Solution {
private:
stack<int> s;
stack<int> smin;
public:
void push(int value) {
if(smin.empty()){
smin.push(value);
}
else if(value<=smin.top()){
smin.push(value);
}
s.push(value);
}
void pop() {
if(s.top()==smin.top()){
smin.pop();
}
s.pop();
}
int top() {
return s.top();
}
int min() {
return smin.top();
}
};
思路2：
不使用輔助棧叹谁，而是使用pair類模板，每次入棧時壓入一個pair對象乘盖，pair對象的first成員初始化為當前要入棧元素焰檩，second成員初始化為當前最小元素值。
class Solution {
private:
typedef pair<int,int> pii;
stack<pii> s;
int smin=0;
public:
void push(int value) {
if(s.empty() || value<=smin){
smin=value;
}
s.push(pii(value,smin));
}
void pop() {
s.pop();
}
int top() {
return s.top().first;
}
int min() {
return s.top().second;
}
};
