一嗡呼、題目描述
題目描述
二朴艰、思路
用雙棧解決瘫辩。一個(gè)棧st正常存取數(shù)據(jù)，另一個(gè)棧minst用以存當(dāng)前最小元素（兩個(gè)棧元素個(gè)數(shù)始終一樣）。
push一個(gè)數(shù)時(shí)進(jìn)行判斷，若該數(shù)比當(dāng)前最小元素還小窗声，那么將其存入minst棧頂，否則將當(dāng)前最小元素再次存入minst棧頂辜纲；
pop操作需要兩個(gè)棧一起pop()笨觅。
三、代碼
class MinStack {
public:
stack<int> st; // 用來(lái)存儲(chǔ)元素
stack<int> minst; // 存儲(chǔ)當(dāng)前最小元素
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
st.push(x);
if(minst.size() == 0){
minst.push(x); // 第一個(gè)元素耕腾，直接存入
}else{
int cur_min = minst.top(); // 當(dāng)前最小元素
if(x < cur_min){ // x比當(dāng)前元素還小
minst.push(x); // 將當(dāng)前最小元素x壓入棧頂
}else{
minst.push(cur_min); // 當(dāng)前最小元素依然不變
}
}
}
void pop() {
st.pop();
minst.pop();
}
int top() {
return st.top();
}
int getMin() {
return minst.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
四见剩、提交結(jié)果
提交結(jié)果
