作者：LeetCode-Solution
鏈接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/solution/bao-han-minhan-shu-de-zhan-by-leetcode-s-i2fk/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)柜思，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處万搔。
方法一：輔助棧
要做出這道題目巷蚪，首先要理解棧結(jié)構(gòu)先進(jìn)后出的性質(zhì)孩革。
對(duì)于棧來(lái)說(shuō)，如果一個(gè)元素a在入棧時(shí)互例，棧里有其他的元素b, c, d，那么無(wú)論這個(gè)棧在之后經(jīng)歷了什么操作唧取，只要a在棧中，b, c, d就一定在棧中划提，因?yàn)樵赼被彈出之前枫弟，b，c鹏往，d不會(huì)被彈出淡诗。
因此，在操作過(guò)程中的任意一個(gè)時(shí)刻伊履，只要棧頂?shù)脑厥莂韩容，那么我們就可以確定棧里面現(xiàn)在的元素一定是a, b, c, d。
那么唐瀑，我們可以在每個(gè)元素a入棧時(shí)把當(dāng)前棧的最小值m存儲(chǔ)起來(lái)群凶。在這之后無(wú)論何時(shí)，如果棧頂元素是a哄辣，我們就可以直接返回存儲(chǔ)的最小值m请梢。
算法
按照上面的思路，我們只需要設(shè)計(jì)完成一個(gè)數(shù)據(jù)結(jié)構(gòu)力穗，使得每個(gè)元素a與其相應(yīng)的最小值m時(shí)刻保持一一對(duì)應(yīng)毅弧。因此我們可以使用一個(gè)輔助棧，與元素棧同步插入或刪除当窗，用于存儲(chǔ)與每個(gè)元素對(duì)應(yīng)的最小值够坐。
- 當(dāng)一個(gè)元素要入棧時(shí)，我們?nèi)‘?dāng)前輔助棧的棧頂存儲(chǔ)的最小值，與當(dāng)前元素比較得出最小值咆霜，將這個(gè)最小值插入輔助棧中。
- 當(dāng)一個(gè)元素要出棧時(shí)嘶朱，我們把輔助棧的棧頂元素也一起彈出蛾坯。
- 在任意一個(gè)時(shí)刻，棧內(nèi)元素的最小值就存儲(chǔ)在輔助棧的棧頂元素中疏遏。
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
s2.push(INT_MAX);
}
void push(int x) {
s1.push(x);
if(x <= s2.top()){
s2.push(x);
}
}
void pop() {
if(s1.top() == s2.top()){
s2.pop();
}
s1.pop();
}
int top() {
return s1.top();
}
int min() {
return s2.top();
}
private:
stack<int> s1;
stack<int> s2;
};
/**
* 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->min();
*/
