``````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.``````

``````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.``````

``````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.``````