一、題目鏈接

最小棧

二、題目

三、算法原理

棧用數組、鏈表實現都行，最主要的就是在能在常數時間內檢索到最小元素的棧，說明getMin是O(1)的接口。

思路1：用一個變量存儲最小元素

用一個變量存儲最小元素，push一個值就比較一下并且要判斷是否要更新最小元素。但是若更新后再pop一下就會出問題，此時棧中最小元素也會發生改變，那么怎么更新呢？更新成什么數呢？遍歷一遍棧嗎，這樣就是O(n)的接口了，與O(1)不符。

思路2：雙棧普通棧和最小棧

采用雙棧的方式來實現：普通棧（正常存取數據）和最小棧。

最小棧：若向普通棧中push的元素大于當前最小棧中的棧頂元素，就不用往最小棧中push；若向普通棧中push的元素小于等于當前最小棧中的棧頂元素或者最小棧為空，就向最小棧中push；getMin獲取最小棧中的棧頂元素即可。

若再push一個與最小元素相等的元素，那么最小棧中是否也要push呢？—— 要。若沒有push，普通棧pop元素-1，此時pop了最小元素，要更新最小值最小棧也pop了，此時最小值理應還是-1而不是1。所以，push的元素比最小棧棧頂元素小或相等，minst都要push這個元素。

當前棧中最小元素是-1，若pop元素7后，最小元素還是-1，此時最小棧不用動。若再pop，此時刪除的元素與最小棧中的棧頂元素相等，那么這時最小棧要pop，這時getMin就是1：

不需要寫構造、析構、拷貝構造、賦值。類的兩個成員變量是自定義類型的，不寫構造，編譯器自動生成的默認構造會自動調用兩個成員變量的默認構造，拷貝構造、析構、賦值同理。

private:stack<int> _st;stack<int> _minst;

構造函數，像這樣啥也不寫或直接為空都是可以的：

因為顯示寫構造了，編譯器就不會生成默認構造了。顯示寫構造，不管有沒有寫初始化列表，一個類都有初始化列表的。沒有顯示寫初始化列表且沒有給缺省值，對于自定義類型的成員會調用它的默認構造。

封裝：
封裝的簡單形態：數據和方法放到類里面，想被看到的封裝成公有，不想被看到的封裝成私有。
另一層封裝的體現：無需關心比如說像這道題的棧的底層是怎么實現的，就只管怎么用即可，知道了功能直接調用對應的功能。

四、編寫代碼

class MinStack {
public:MinStack(){}void push(int val) {_st.push(val);if (_minst.empty() || val <= _minst.top()) _minst.push(val);}void pop() {if (_st.top() == _minst.top()) _minst.pop();_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;stack<int> _minst;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

五、時間復雜度

所有接口的時間復雜度都是O(1)。