Min Stack

LeetCode Q 155 - 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.

Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> Returns -3.
minStack.pop();
minStack.top(); –> Returns 0.
minStack.getMin(); –> Returns -2.

Solution

Solution 1 :

Use a variable min to track the previous minimum Value, and use the stack to store the difference of the current value to minimumvalue, i.e. num - min.
Therefore if the value in the stack is negative, that means, the current value is less than the min.

Note: This method is cannot pass the test case, i.e.
[“MinStack”,”push”,”push”,”push”,”top”,”pop”,”getMin”,”pop”,”getMin”,”pop”,”push”,”top”,”getMin”,”push”,”top”,”getMin”,”pop”,”getMin”]
[[],[2147483646],[2147483646],[2147483647],[],[],[],[],[],[],[2147483647],[],[],[-2147483648],[],[],[],[]]

Code:

private Stack<Integer> stack;
private Integer min;

/ ** initialize your data structure here. * /
public MinStack() {
	min = Integer.MAX_VALUE;
	stack = new Stack<>();
}

public void push(int x) {
	if (stack.isEmpty()) {
		stack.push(0); min = x;
	} else {
		stack.push(x - min);
		min = Math.min(x, min);
	}
}

public void pop() {
	int num = stack.pop();
	if (num < 0) 
		min = min - num;
}

public int top() {
	return stack.peek() + min;
}

public int getMin() {
	return min;
}

Solution 2 :

Use two stacks, one is Monotonous stack.

Code:

private Stack<Integer> stack;
private Stack<Integer> minStack;

/ ** initialize your data structure here. * /
public MinStack() {
	stack = new Stack<>();
	minStack = new Stack<>();
}

public void push(int x) {
	stack.push(x);
	if (minStack.isEmpty()) {
		minStack.push(x);
	} else if (minStack.peek() >= x) {
		minStack.push(x);
	}
}

public void pop() {
	int num = stack.pop();
	if (num == minStack.peek())
		minStack.pop();
}

public int top() {
	return stack.peek();
}

public int getMin() {
	return minStack.peek();
}

Solution 3 : OOD

Code:

class Node {
	int val, min;
	Node next;
	
	public Node (int val, int min, Node next) {
		this.val = val; this.min = min; this.next = next;
	}

	public Node (int val, int min) {
		this(val, min, null);
	}
}

/ ** initialize your data structure here. * /
public MinStack() {
}

private Node head;

public void push(int x) {
	if (this.head == null)
		this.head = new Node(x, x);
	else 
		this.head = new Node(x, Math.min(x, this.head.min), this.head);
}

public void pop() {
	if (head == null)
		return;
	head = head.next;
}

public int top() {
	return head.val;
}

public int getMin() {
	return head.min;
}