Min Stack

leetcode 155.

There are many ways to solve the min stack problem. However, there is one solution which only requiring O(1) extra space.

The idea is that when pushinng, store the offset of the current min value. When pop or getTop, use the offset and min to get the top or next min.

If the [3, 4, 2, 1] enters stack sequentially, the stack looks like this:

public class MinStack {

    long min;
    Stack<Long> stack;

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

    public void push(int x) {
        if (stack.size() == 0) {
            min = x;
            stack.push(0l);
        }
        else {
            stack.push(x - min);
            min = Math.min(min, x);
        }
    }

    public void pop() {
        long pop = stack.pop();
        if (pop < 0) {
            min = min - pop;
        }
    }

    public int top() {
        long top = stack.peek();
        if (top < 0) {
            return (int)min;
        }
        return (int)(top + min);
    }

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

}

Check my code on github.