題目描述 [最小棧]
設(shè)計(jì)一個(gè)支持 push，pop，top 操作碘裕，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
- push(x) -- 將元素 x 推入棧中攒钳。
- pop() -- 刪除棧頂?shù)脑亍?/li>
- top() -- 獲取棧頂元素帮孔。
- getMin() -- 檢索棧中的最小元素。
示例
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解題思路
轉(zhuǎn)自 https://www.cnblogs.com/jlxuexijidi-2015/p/4946223.html
用一個(gè)輔助棧來(lái)實(shí)現(xiàn)最小值的更新工作不撑。
這個(gè)輔助棧工作原理：
入棧時(shí)文兢，1）當(dāng)數(shù)據(jù)棧為空時(shí)，進(jìn)入棧的元素同時(shí)也進(jìn)入輔助棧燎孟；2）當(dāng)它不為空時(shí)禽作，就把該入棧元素與輔助棧的棧頂元素進(jìn)行比較尸昧，若入棧元素小揩页，則該元素同時(shí)也進(jìn)入輔助棧；若不是烹俗，則對(duì)輔助棧不進(jìn)行操作
出棧時(shí)爆侣，1）當(dāng)時(shí)輔助棧的棧頂元素等于處理數(shù)據(jù)的數(shù)據(jù)棧棧頂元素時(shí)，不經(jīng)數(shù)據(jù)棧要彈出元素幢妄，輔助棧也要彈出棧頂元素兔仰，2)當(dāng)不等時(shí)，只對(duì)數(shù)據(jù)棧進(jìn)行出棧操作蕉鸳。
min函數(shù)只需返回輔助棧的棧頂源乎赴。
代碼
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {}
void push(int x) {
s1.push(x);
if (s2.empty() || x <= s2.top()) s2.push(x);
}
void pop() {
if (s1.top() == s2.top()) s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
private:
stack<int> s1, s2;
};