# Min Stack

https://leetcode.com/problems/min-stack/description/

## Question

LintCode

Implement a stack with `min()` function, which will return the smallest number in the stack.

It should support `push`, `pop` and `min` operation all in `O(1)` cost.

Notice

`min` operation will never be called if there is no number in the stack.

Example

``````push(1)
pop()   // return 1
push(2)
push(3)
min()   // return 2
push(1)
min()   // return 1
``````

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.

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

Using Two Stacks

min = Integer.parseInt(minStack.peek().toString());

push()时，如果number <= min，则push到minStack上
pop()时，如果number == min，也从minStack上pop

Using Single Stack

The problem for the solution is the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;

## Solution

``````public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;

public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}

public void push(int number) {
stack.push(number);
if (minStack.isEmpty()) {
minStack.push(number);
} else if (Integer.parseInt(minStack.peek().toString()) >= number) {
minStack.push(number);
}
}

public int pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
return stack.pop();
}

public int min() {
return minStack.peek();
}
}
``````
##### Using Two Stacks*

https://stackoverflow.com/questions/3637936/java-integer-equals-vs

The JVM is caching Integer values. `==` only works for numbers between `-128` and `127`

http://www.owasp.org/index.php/Java_gotchas#Immutable_Objects_.2F_Wrapper_Class_Caching

You can't compare two`Integer`with a simple `==` they're objects so most of the time references won't be the same.

There is a trick, with `Integer` between -128 and 127, references will be the same as autoboxing uses`Integer.valueOf()`which caches small integers.

``````// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
Stack<Integer> t = new Stack<>();
s.push(-1);
t.push(-1);
System.out.println(s.pop() == t.pop());

s.push(-129);
t.push(-129);
System.out.println(s.pop() == t.pop());

s.push(128);
t.push(128);
System.out.println(s.pop() == t.pop());
}
}

// output:
// true
// false
// false
``````

--

Time: O(1)

Space: O(n)

``````class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;

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

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

public void pop() {
int x = stack.pop();
if (!minStack.isEmpty() && x == minStack.peek()) {
minStack.pop();
}
}

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

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

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
``````
##### Using One Stack - store difference between x and min
• Time: O(1)
• Space: O(1)

top() - 如果当前栈顶的对应元素是新的min值，那么 top() 对应 min, 否则对应 stack.peek() + min

push() - 每次存入

``````public class MinStack {
long min;
Stack<Long> stack;

public MinStack() {
min = Integer.MAX_VALUE;
stack  = new Stack<>();
}

public void push(int x) {
stack.push((long)x - min);
min = Math.min(x, min);
}

public void pop() {
min = Math.max(min - stack.pop(), min);
}

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

public int getMin() {
return (int)min;
}
}
``````
##### Using One Stack with Custom Element Class Object - Store min within each element

Time: O(1)

Space: O(n), extra space for the min value in the custom class object

``````class MinStack
{
static class Element
{
final int value;
final int min;
Element(final int value, final int min)
{
this.value = value;
this.min = min;
}
}
final Stack<Element> stack = new Stack<>();

public void push(int x) {
final int min = (stack.empty()) ? x : Math.min(stack.peek().min, x);
stack.push(new Element(x, min));
}

public void pop()
{
stack.pop();
}

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

public int getMin()
{
return stack.peek().min;
}
}
``````

``````class MinStack {

public void push(int x) {
head = new Node(x, x);
else
}

public void pop() {
}

public int top() {
}

public int getMin() {
}

private class Node {
int val;
int min;
Node next;

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

private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
``````

## Reference

https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/