Programming Skills: Min Stack

[題目]

https://leetcode.com/problems/min-stack/description/
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Push, pop and getMin should all operate in O(1) time

也就是說你要做一個特別的stack，他除了擁有一般stack的功能，還額外有一個getMin()會return目前stack中最小的element value，是get不是pop喔，並沒有要消除那個元素。

[思路]

要做並不難，做一個一般的stack，getMin()時把stack中的element全都倒出來找min，找完再塞回stack就好。這想法很直觀。但問題是time complexity=O(N)，而題目要求要O(1)完成getMin()。

[O(1)思路]

我們舉例觀察一下min這件事情

e.g.

push 7 min =7

push 3 min =3

push 2 min =2

push 4 min =2

push 1 min =1

min = 1

pop 1 min = 2

pop 4 min = 2

pop 2 min = 3

pop 3 min = 7

pop 7 min = N/A

你如果單獨觀察上例min的部分，會發現他運作起來也像個stack。沒錯我們只要額外加一個stack來處理min就好了。然後從理論上來解釋這個minstack，它當中存放的東西是"目前為止的min value"。當normal stack push一個new element，我就增加一個"目前為止的min value"。當normal stack pop一個element，minstack也pop一個"目前為止的min value"。

ps.這個做法是用空間換取時間，多了一倍的space。但push時可以優化，先比較大小再決定要不要push到min_stack。


class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> minstack;
    MinStack() {
        
    }
    
    void push(int x) {
        s.push(x);
        if(minstack.empty()) 
            minstack.push(x);
        else{
            if(minstack.top() >= x)
                minstack.push(x);
        }
    }
    
    void pop() {
        if(minstack.top() == s.top()) minstack.pop();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return minstack.top();
    }
};