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

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 twoIntegerwith 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 usesInteger.valueOf()which caches small integers.

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

参考：

// "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;
    }
}

Using LinkedList Node*

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/