Stack with max API
class MaxStack {
public:
/** initialize your data structure here. */
MaxStack() {
}
void push(int x) {
int max = maxs.empty() ? x : maxs.back();
maxs.push_back(max > x ? max : x);
stack.push_back(x);
}
int pop() {
int back = stack.back();
stack.pop_back();
maxs.pop_back();
return back;
}
int top() {
return stack.back();
}
int peekMax() {
return maxs.back();
}
int popMax() {
int max = peekMax();
std::vector<int> buffer;
while(top() != max)
{
buffer.push_back(pop());
}
pop();
while(!buffer.empty())
{
push(buffer.back());
buffer.pop_back();
}
return max;
}
private:
std::vector<int> stack;
std::vector<int> maxs;
};