[LeetCode] Min Stack

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution: The most space-efficient way is to use two stacks s1 and s2: s1 for all the elements, and s2 for all the minimums. 
The key invariant: The minimum of all the elements in s1 will always be the top element of s2.
Remarks: You may find the detailed description of this solution in the book: Cracking the Coding Interview: 150 Programming Questions and Solutions (5th edition). An electronic copy of the 4th version may be found online.

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

class MinStack { private Stack<Integer> s1; private Stack<Integer> s2; public MinStack() { s1 = new Stack<Integer>(); s2 = new Stack<Integer>(); } public void push(int x) { s1.push(x); if (s2.empty() || x <= s2.peek()) { s2.push(x); } } public void pop() { if (s1.peek() == getMin()) { s2.pop(); } s1.pop(); } public int top() { return s1.peek(); } public int getMin() { return s2.peek(); } }