題目要求：自定義棧的數(shù)據(jù)結(jié)構(gòu)
實現(xiàn)push、pop、min函數(shù)，其中min函數(shù)可以得到棧中的最小元素
要求：調(diào)用 min、push 及 pop 的時間復(fù)雜度都是 O(1)

解題思路：
創(chuàng)建兩個棧，棧1用來保證基礎(chǔ)的push、pop、top操作，棧2用來實現(xiàn)min函數(shù)的功能。
其中棧2的思路：只壓入比棧2棧頂小的元素（如果當(dāng)前元素比棧2棧頂大，可以理解為：它是否彈出對min函數(shù)沒有任何貢獻(xiàn)）

圖解

C++

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

Java

class MinStack {

    /** initialize your data structure here. */
    public MinStack() {
        s1 = new LinkedList<Integer>();
        s2 = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        s1.addLast(x);
        if(s2.isEmpty() || !s2.isEmpty() && s2.getLast() >= x) s2.addLast(x);
    }
    
    public void pop() {
        int e = s1.removeLast();
        if(e == s2.getLast()) s2.removeLast();
    }
    
    public int top() {
        return s1.getLast();
    }
    
    public int min() {
        return s2.getLast();
    }
    LinkedList<Integer> s1;
    LinkedList<Integer> s2;
}