Design a max stack that supports push, pop, top, peekMax and popMax.
- push(x) -- Push element x onto stack.
- pop() -- Remove the element on top of the stack and return it.
- top() -- Get the element on the top.
- peekMax() -- Retrieve the maximum element in the stack.
- 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:
- -1e7 <= x <= 1e7
- Number of operations won't exceed 10000.
- 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(); */ |
No comments:
Post a Comment