# 716. Max Stack 最大栈

@TOC

## # 题目描述

Design a max stack that supports push, pop, top, peekMax and popMax.

1. `push(x)` -- Push element x onto stack.
2. `pop()` -- Remove the element on top of the stack and return it.
3. `top()` -- Get the element on the top.
4. `peekMax()` -- Retrieve the maximum element in the stack.
5. `popMax()` -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

``````MaxStack stack = new MaxStack();
stack.push(5);
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5
``````

Note:

1. `-1e7 <= x <= 1e7`
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

## # 解题方法

### # 双栈

C++代码如下：

``````class MaxStack {
public:
/** initialize your data structure here. */
MaxStack() {
}

void push(int x) {
if (!maxVals.empty() && x < maxVals.top()) {
maxVals.push(maxVals.top());
} else {
maxVals.push(x);
}
values.push(x);
}

int pop() {
int val = values.top();
values.pop();
maxVals.pop();
return val;
}

int top() {
return values.top();
}

int peekMax() {
int maxv = maxVals.top();
return maxv;
}

int popMax() {
int maxv = maxVals.top();
stack<int> temp;
while (!values.empty() && values.top() != maxv) {
temp.push(values.top());
values.pop();
maxVals.pop();
}
values.pop();
maxVals.pop();
while (!temp.empty()) {
push(temp.top());
temp.pop();
}
return maxv;
}
private:
stack<int> values;
stack<int> maxVals;
};

/**
* Your MaxStack object will be instantiated and called as such:
* MaxStack* obj = new MaxStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->peekMax();
* int param_5 = obj->popMax();
*/
``````

## # 日期

2019 年 9 月 19 日 —— 举杯邀明月，对影成三人