716. Max Stack

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.

与MinStack 类似，定义两个栈，一个存放元素，另一个存放对应一层的最大值。 关键是 popMax() 的实现，怎么从栈里弹出某一个值。 可以定义一个临时stack，不断从stack中pop出元素，放到tmp栈中，直到弹到最大值那一刻停下，然后再把tmp里的元素往stack里放回即可。

class MaxStack { Stack<Integer> stack = new Stack<>(); Stack<Integer> maxStack = new Stack<>(); /** initialize your data structure here. */ public MaxStack() { } public void push(int x) { stack.push(x); if (!maxStack.isEmpty()) { if (x >= maxStack.peek()) { maxStack.push(x); } else { maxStack.push(maxStack.peek()); } } else { maxStack.push(x); } } public int pop() { int e = stack.pop(); maxStack.pop(); return e; } public int top() { return stack.peek(); } public int peekMax() { return maxStack.peek(); } public int popMax() { int curMax = maxStack.peek(); Stack<Integer> tmp = new Stack<>(); while (stack.peek() != curMax) { int num = stack.pop(); maxStack.pop(); tmp.push(num); } stack.pop(); maxStack.pop(); while (!tmp.isEmpty()) { push(tmp.pop()); } return curMax; } }