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.

我的第一想法是使用一个链表来解决问题,但我看更多人的题解是使用了栈类来做,只可惜我没用过💩。这里使用链表就可以轻松解决四个函数中的三个,而最后一个最小值的函数,则借助于链表节点本身来解决,即增加一个变量来保存栈中当前的最小值。

/*
 * 155. Min Stack
 * https://leetcode.com/problems/min-stack/
 * https://realneo.me/155-min-stack/
 */

public class MinStack {
    private Node head = null;

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }

    private void push(int x) {
        Node node = new Node();
        node.value = x;
        if (head == null || x < head.min)
            node.min = x;
        else
            node.min = head.min;
        node.next = head;
        head = node;
    }

    private void pop() {
        if (head != null)
            head = head.next;
    }

    private int top() {
        if (head != null)
            return head.value;
        else
            return 0;
    }

    private int getMin() {
        if (head != null)
            return head.min;
        else
            return 0;
    }

    static class Node {
        int value;
        int min;
        Node next;
    }
}