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.

//
// Created by simida on 2020/07/12.
//// 加锁题，未经OJ测试// time complexity
// space complexity O(n)#include <stdio.h>
#include <iostream>
#include <stack>
using namespace std;class MaxStack {private:stack<int> stack_;stack<int> help_stack_; // 辅助最大值栈public:/** initialize your data structure here. */MaxStack() {}void push(int x) {stack_.push(x);if (help_stack_.empty()) {help_stack_.push(x);} else if (x > help_stack_.top()) {help_stack_.push(x);} else {int top = help_stack_.top();help_stack_.push(top);}}void pop() {stack_.pop();help_stack_.pop();}int top() {return stack_.top();}int peekMax() {return help_stack_.top();}int popMax() {stack<int> s;	// 临时栈int top = help_stack_.top();// 将最大值上面的元素放入临时栈，然后弹出￿最大值即可while (stack_.top() != top) {s.push(stack_.top());stack_.pop();}stack_.pop(); // 将stack_最顶端的最大值弹出// 将最大值栈help_stack_的最大值弹出while (!help_stack_.empty() && help_stack_.top() == top) {help_stack_.pop();}// 对于stack_: 将临时栈s中的元素重新放回stack_中// 对于help_stack_: 重新生成最大值栈while (!s.empty()) {push(s.top());s.pop();}return top;}
};int main() {
// Your MaxStack object will be instantiated and called as such:MaxStack* obj = new MaxStack();obj->push(5);printf("top is %d\n", obj->top()); // 5obj->push(4);printf("top is %d\n", obj->top()); // 4obj->push(3);printf("top is %d\n", obj->top()); // 3obj->push(2);printf("top is %d\n", obj->top()); // 2obj->push(1);printf("top is %d\n", obj->top()); // 1printf("\nstop push\n");obj->popMax();printf("top is %d\n", obj->top()); // 1printf("peekMax is %d\n", obj->peekMax()); // 4obj->popMax();printf("top is %d\n", obj->top()); // 1printf("peekMax is %d\n", obj->peekMax()); // 3obj->popMax();printf("top is %d\n", obj->top()); // 1printf("peekMax is %d\n", obj->peekMax()); // 2obj->pop();printf("top is %d\n", obj->top()); // 2
}