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.
 
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:
Methods pop, top and getMin operations will always be called on non-empty stacks.

老规矩，先以最快速度AC，然后再想优化的方法，运行结果产不忍赌,仅击败5.05%。

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        stack.push_back(x);
    }
    
    void pop() {
        stack.pop_back();
    }
    
    int top() {
        return stack.back();
    }
    
    int getMin() {
        int min = stack.back();
        for(auto it = stack.begin();it != stack.end();it++)
        {
            if(min > *it)
                min = *it;
        }
        
        return min;
    }
private:
    vector<int> stack;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

Runtime: 1104 ms, faster than 5.05% of C++ online submissions for Min Stack.
Memory Usage: 16.2 MB, less than 38.74% of C++ online submissions for Min Stack.

优化后的解法：

class MinStack {
private:
    stack<int> s1;
    stack<int> s2;
public:
    void push(int x) {
        s1.push(x);
        if (s2.empty() || x <= getMin())  s2.push(x);
    }
    void pop() {
        if (s1.top() == getMin())  s2.pop();
        s1.pop();
    }
    int top() {
        return s1.top();
    }
    int getMin() {
        return s2.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

运行结果：

Runtime: 56 ms, faster than 31.37% of C++ online submissions for Min Stack.
Memory Usage: 16.2 MB, less than 32.65% of C++ online submissions for Min Stack.

这里相当于用两个栈实现getMin复杂度O(1),以空间换时间，一个栈保存数据，另一个栈维护按照插入顺序记录的最小数据，这样pop数据之后需要相应的更新s2.
在讨论区看到另一种高效解法：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        min = INT_MAX;
    }
    
    void push(int x) {
        if(x <= min) {
            stack.push_back(min);
            min = x;
        }
        stack.push_back(x);
    }
    
    void pop() {
        int t = stack.back(); 
        stack.pop_back();
        if (t == min) {
            min = stack.back();
            stack.pop_back();
        }
    }
    
    int top() {
        return stack.back();
    }
    
    int getMin() {
        return min;
    }
private:
    vector<int> stack;
    int min;
};    

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

Runtime: 20 ms, faster than 100.00% of C++ online submissions for Min Stack.
Memory Usage: 16.2 MB, less than 30.92% of C++ online submissions for Min Stack.

2021.03.14更新,最直观的写法：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        elem.push_back(x);
        min_elem = min(min_elem,x);
    }
    
    void pop() {
        int val = elem.back();
        elem.pop_back();
        if(val == min_elem)
        {
            min_elem = INT_MAX;
            for(int i = 0;i<elem.size();i++)
                min_elem = min(min_elem,elem[i]);
        }
        
    }
    
    int top() {
        int val = elem.back();
        return val;
    }
    
    int getMin() {
        return min_elem;
    }
private:
    vector<int> elem;
    int min_elem = INT_MAX;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

运行效率：

Runtime: 16 ms, faster than 98.64% of C++ online submissions for Min Stack.
Memory Usage: 16 MB, less than 62.66% of C++ online submissions for Min Stack.