# 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**

利用两个栈结构，其中一个是主要的正常stack，满足pop(), push()的O(1)时间要求，另外一个作为辅助的minStack，仅存入min的integer。\
min = Integer.parseInt(minStack.peek().toString());

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

题中的例子，最终stack为\[2, 3, 1], minStack为 \[2, 1]

这样minStack中保留stack中最小元素相对顺序，在pop之后依然能够保证minStack的栈顶为当前最小元素。

**Using LinkedList Node**

自定义Node类，其中包含该节点对应的min，这样就可以实现O(1)的getMin()操作，其余push(), pop()，也因为LinkedList实现O(1)

**Using Single Stack**

这个想法较为奇特一些，就是在stack中存入当前入栈的值与最小值之差，`x - min`

优点是getMin() 操作只需返回min即可，但是push(), pop() 操作需要结合min以及栈顶元素

缺点是：

> 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

```java
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\***

**注意**：这里有一个trick要注意，因为stack中存入的是Integer，因此 pop()时，检查是否minStack和stack中的元素是否相等时，需要做强制转化为(int) 变量，否则会出现错误（当元素范围在`-128 ~ 127`之外时）：

<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.

因此，可以先用int强制转化。

参考：

```java
// "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)

```java
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)&#x20;

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

push() - 每次存入

```java
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

```java
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;
    }
}
```

**Using LinkedList Node\***

```java
class MinStack {
    private Node head;

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

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

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

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

    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/>