I think almost everyone has came up with the two-stack structure to solve this problem.

But at the first time, I have got "memory limit exceeded" with following code:

```
class MinStack {
public:
MinStack() {
data.clear();
min_element.clear();
}
void push(int x) {
data.push_back(x);
if(min_element.empty() || min_element.back() > x)
min_element.push_back(x);
else
min_element.push_back(min_element.back());
}
void pop() {
if(data.empty())
return;
data.pop_back();
min_element.pop_back();
}
int top() {
return data.back();
}
int getMin() {
return min_element.back();
}
private:
deque<int> data;
deque<int> min_element; //maintain the minimum element
};
```

Space complexity is O(2n) because *min_element* increases simultaneously with *data*. I believe there must be a "coincident case" which exhausts the memory.

Then I try to rewrite *pop()* and *push()*:

```
void push(int x) {
data.push_back(x);
/*"min_element" push only happens when comes a smaller element.
Remember the '>=' cannot be '>'.*/
if(min_element.empty() || min_element.back() >= x)
min_element.push_back(x);
}
void pop() {
if(data.empty())
return;
int tmp = data.back();
data.pop_back();
/*pop when a current minimum element is pop out.*/
if(tmp == min_element.back())
min_element.pop_back();
}
```

This time the best space complexity is O(n).

Hope it will help. Any comment is welcome.