最小棧
- 一、題目鏈接
- 二、題目
- 三、算法原理
- 思路1:用一個變量存儲最小元素
- 思路2:雙棧普通棧和最小棧
- 四、編寫代碼
- 五、時間復雜度
一、題目鏈接
最小棧
二、題目
三、算法原理
棧用數組、鏈表實現都行,最主要的就是在能在常數時間內檢索到最小元素的棧,說明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)。