The difference between max stack and min stack is the `popMax()`

function. When we pop element, we just have to check whether the tops of `maxStk`

and `stk`

are the same or not. It costs O(1) time in this operation.

However, in the case of `popMax()`

, the top of `maxStk`

may not be the same as the top of `stk`

. Therefore, the idea here is to use `tmp`

stack to store the element of `stk`

until we find the max element, remove it. Then, we put the elements in `tmp`

back to `stk`

and `maxStk`

. It costs `O(n)`

in worst case.

```
class MaxStack {
public:
/** initialize your data structure here. */
MaxStack() {
}
void push(int x) {
addMax(x);
stk.push(x);
}
int pop() {
int val = stk.top();
if (stk.top() == maxStk.top()) {
maxStk.pop();
}
stk.pop();
return val;
}
int top() {
return stk.top();
}
int peekMax() {
return maxStk.top();
}
int popMax() {
int val = maxStk.top();
stack<int> tmp;
while (maxStk.top() != stk.top()) {
tmp.push(stk.top());
stk.pop();
} // maxStk.top() == stk.top()
maxStk.pop();
stk.pop();
while (!tmp.empty()) {
stk.push(tmp.top());
addMax(tmp.top());
tmp.pop();
}
return val;
}
private:
void addMax(int x) {
if (maxStk.empty() || x >= maxStk.top()) {
maxStk.push(x);
}
}
stack<int> maxStk;
stack<int> stk;
};
```