classMaxStack{ Stack<Integer> stack = new Stack<>(); Stack<Integer> buffer = new Stack<>(); privateint max = Integer.MIN_VALUE;

publicvoidpush(int x){ stack.push(x); if (x > max) { max = x; } }

publicintpop(){ // assume not empty int val = stack.pop(); if (val == max) { // update max (find the new max) int newMax = Integer.MIN_VALUE; // consider size = 1, min should be reset // put aside while (stack.size() > 0) { int x = stack.pop(); newMax = Math.max(newMax, x); buffer.push(x); } max = newMax; // put it back while (buffer.size() > 0) { stack.push(buffer.pop()); } } return val; }

publicinttop(){ return stack.peek(); }

publicintpeekMax(){ return max; }

publicintpopMax(){ int newMax = Integer.MIN_VALUE; // find the max while (stack.peek() != max) { newMax = Math.max(newMax, stack.peek()); buffer.push(stack.pop()); } // remove max stack.pop(); // still put all to the buffer (we want to find newMax) while (stack.size() > 0) { newMax = Math.max(newMax, stack.peek()); buffer.push(stack.pop()); } // put back while (buffer.size() > 0) { stack.push(buffer.pop()); } int oldMax = max; max = newMax; return oldMax; } }

publicintpopMax(){ int max = maxStack.peek(); while (stack.peek() != max) { buffer.push(pop()); // pop from two stacks } pop(); // remove max while (buffer.size() > 0) { push(buffer.pop()); // push into two stacks } return max; } }

Note:

The following popMax() is not correct. Why? Use stack.pop() or pop()? Or use which push()?

1 2 3 4 5 6 7 8 9 10 11

// bug! publicintpopMax(){ while (stack.peek() != maxStack.peek()) { buffer.push(stack.pop()); } stack.pop(); // remove max while (buffer.size() > 0) { stack.push(buffer.pop()); } return maxStack.pop(); }

Time: Only popMax() takes $O(N)$ Space: $O(N)$

The optimization can be made in finding the largest element by TreeMap.