# 155 - Min Stack

解法一 - 兩個 stack

這個解法不算很直覺，但還是有機會想得到。一開始，我們直覺可能會想要用一個 int variable 來儲存目前 min stack 裡面的最小值，但問題來了，如果這個最小值剛好被 pop 出來了要怎麼辦？

所以我們需要一個方法來記錄最小值以外的另一個最小值，而這邊就可以用另一個 stack 來存最小值。

以下圖的例子來說，步驟分別是：

1. 看到 -2，因為 -2 是目前最小值，所以放入 stk 跟 minStk

2. 看到 0，因為 0 比 -2 大，所以只放入 stk 這時，minStk 裡的 -2 負責了 -2 到 0 這一段的最小值，所以即使 0 這時被 pop 出來，也不影響最小值

3. 看到 -3，因爲 -3 比 minStk.top(也就是 -2)還要小，所以也放進 Stk 跟 MinStk

程式碼實作如下：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }

    void push(int x) {
        if(minStk.empty() or x <= getMin()) minStk.push(x);
        stk.push(x);
    }

    void pop() {
        if(stk.top() == getMin()) minStk.pop();
        stk.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return minStk.top();
    }

private:
    stack<int> minStk ;
    stack<int> stk;
};