# Leetcode: 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.
```

## Analysis

For O(1) pop, push, a normal stack can serve this purpose. But a little hard for O(1) get min.

However, noticed that this is still a stack, can not just pop node with min value. So we can record min value on each node when pushing into this stack.

e.g. as the example above:

1. push -2
-2(-2) — means the node has value -2 and the min value as of now in the stack is -2.
2. push 0
0(-2) -> -2(-2)
3. push -3
-3(-3) -> 0(-2) -> -2(-2)
4. getMin return -3 (in the parenthesis)
5. pop
0(-2) -> -2(-2)
6. top, return 0
7. getMin return -2

## Solutions

### Java

```class MinStack {

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

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

public void push(int x) {
Node newNode = new Node(x);
newNode.min = newNode.next != null && newNode.next.min.value < newNode.value ? newNode.next.min : newNode;
}

public void pop() {
}
}

public int top() {
} else {
return Integer.MAX_VALUE;
}
}

public int getMin() {