0 引言
題目：定義棧的數據結構，請在該類型中實現一個能夠得到棧的最小元素的min函數。在該棧中，調用min、push及pop的時間復雜度都是O（1）. 1 抽象問題具體化
2 具體問題抽象分析
需要解決的兩個主要問題如下。
（1）如何在復雜度O（1）的條件下，返回當前棧的最小值。解決思路是定義一個minNum變量保存當前棧的最小值。
（2）另外一個問題是如果當前最小值被彈出了，如何更新minNum的值。解決思路是定義一個新的棧，該棧用于保存次小的值。涉及到兩步操作：
1）什么時候入棧：當前入棧的值小于等于最小值時，入棧
2）什么時候出棧：當前出棧值等于最小值時，更新最小值，出棧
3 demo
stack<int> myStack; // 數據棧stack<int> minorMinNum; // 輔助棧int minNum = 99999999; // 最小值void push(int value) {if(value <= minNum){ // 只有滿足當前入棧值小于等于最小值的條件，才將該值壓入輔助棧中，同時更新最小值 minorMinNum.push(value);minNum = value; } myStack.push(value);}void pop() {int temp;if(!myStack.empty()){temp = myStack.top();myStack.pop();} if(!minorMinNum.empty()){ if(temp == minNum){ // 只有滿足當前出棧值等于最小值的條件，更新最小值，同時輔助棧出棧 minorMinNum.pop();minNum = minorMinNum.top(); } }}int top() {return myStack.top();}int min() {return minNum;}
4 代碼優化
可以將上述變量minNum給省掉，寫法精簡如下。
?
stack<int> myStack;stack<int> minorMinNum;void push(int value) {if(minorMinNum.empty()){minorMinNum.push(value);}else if(value <= minorMinNum.top())minorMinNum.push(value); myStack.push(value);}void pop() { if(!myStack.empty() && !minorMinNum.empty()){if(myStack.top() == minorMinNum.top())minorMinNum.pop();myStack.pop();}}int top() {return myStack.top();}int min() {return minorMinNum.top();}
?
