The key idea is use a another stack to store the minimum value
of the corresponding stack. Put differently, min[i]
equals the minimum element where data[i]
is the top of this substack.
We can use a full size of min
where its size equals the data's, but it's not necessary.
Idea

We should
pop
the element inmin
IFF there's match ofdata.top()
. 
If we have multiple same minima, for example
[0, 1, 0]
indata
, then themin
should be[0, 0]
.
Otherwise, the thepop
operation wouldn't work properly, since that you need 20
s.
As a result, we should push the element ifx <= min.top()
.
Code
class MinStack {
stack<int> data;
stack<int> min;
public:
void push(int x) {
// If empty
if (min.empty()) {
data.push(x);
min.push(x);
}
// Not empty
else {
data.push(x);
if (x <= min.top())
min.push(x);
}
}
void pop() {
if (!min.empty()) {
if (data.top() == min.top())
min.pop();
data.pop();
}
}
int top() {
return data.top();
}
int getMin() {
return min.top();
}
};