155. Min Stack

解題思路

要 getMin，就要想方法去紀錄最小值。沒辦法只用一個變數記錄當下最小值，因為如果 pop 掉的剛好是最小值，那要如何再回溯找到上一個最小值？

所以會需要另一個 stack，用來記錄當下以這個 element 為 top 時，最小值是誰？然後每當有 push 或 pop ，要同步更新。

程式碼

class MinStack {
public:
    stack<int> st;
    stack<int> minSt; // record the min value at that point

    MinStack() {
        
    }
    
    void push(int val) {
        st.push(val);
        if(minSt.empty())
            minSt.push(val);
        else if(val < minSt.top())
            minSt.push(val);
        else
            minSt.push(minSt.top());
    }
    
    void pop() {
        st.pop();
        minSt.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minSt.top();
    }
};