LeetCode [716] Max Stack

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

class MaxStack { stack<int> stk, stkM; public: /** initialize your data structure here. */ MaxStack() { } void push(int x) { stk.push(x); if(stkM.empty() || x>=stkM.top()) stkM.push(x); } int pop() { int v = stk.top(); stk.pop(); if(stkM.top()==v) stkM.pop(); return v; } int top() { return stk.top(); } int peekMax() { return stkM.top(); } int popMax() { int v = stkM.top(); stkM.pop(); if(v==stk.top()){ stk.pop(); }else{ stack<int> tmp; while(!stk.empty() && stk.top()!=v){ tmp.push(stk.top()); stk.pop(); } stk.pop(); while(!tmp.empty()){ stk.push(tmp.top()); if(stkM.empty() || tmp.top()>=stkM.top()) stkM.push(tmp.top()); tmp.pop(); } } return v; } }; /** * 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(); */