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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/stack/min_stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.