Min Stack @LeetCode

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.

	import java.util.HashMap;
	import java.util.Map;
	import java.util.Stack;
	public class MinStack {
	// retrieving the minimum element in constant time.
	Stack<Integer> stack = new Stack<Integer>();
	Stack<Integer> minStack = new Stack<Integer>();
	Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
	public void push(int x) {
	if (x == getMin()) {
	cache.put(x, cache.get(x) + 1);
	}
	if (x < getMin()) {
	minStack.push(x);
	cache.put(x, 1);
	}
	stack.push(x);
	}
	public void pop() {
	int value = stack.pop();
	if (value == getMin()) {
	if (cache.get(value) == 1) {
	minStack.pop();
	}
	cache.put(value, cache.get(value) - 1);
	}
	}
	public int top() {
	return stack.peek();
	}
	public int getMin() {
	if (minStack.isEmpty()) {
	return Integer.MAX_VALUE;
	} else {
	return minStack.peek();
	}
	}

view raw MinStack.java hosted with ❤ by GitHub