LeetCode--Min Stack

題目：

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.

解決方案一：

class MinStack {
    private Stack mStack = new Stack();
private Stack mMinStack = new Stack();

public void push(int x) {
    mStack.push(x);
    if (mMinStack.size() != 0) {
        int min = mMinStack.peek();
        if (x <= min) {
            mMinStack.push(x);
        }
    } else {
        mMinStack.push(x);
    }
}

public void pop() {
    int x = mStack.pop();
    if (mMinStack.size() != 0) {
        if (x == mMinStack.peek()) {
            mMinStack.pop();
        }
    }
}

public int top() {
    return mStack.peek();
}

public int getMin() {
    return mMinStack.peek();
}
}

ps：方案一的疑惑

第一次見到這個解決方案的時候，總是感覺怪怪的總覺它是有問題的，特別是push方法的這兩句 int min = mMinStack.peek();
if (x <= min) {
mMinStack.push(x);
} 之後在一篇博文裡給了我解決這個疑惑的答案。

博文裡的分析：

這道題的關鍵之處就在於 minStack 的設計，push() pop() top() 這些操作Java內置的Stack都有，不必多說。
我最初想著再弄兩個數組，分別記錄每個元素的前一個比它大的和後一個比它小的，想復雜了。
第一次看上面的代碼，還覺得它有問題，為啥只在 x
方案二（效率較高，容易理解）：
class MinStack {
    Node top = null;

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

    public void pop() {
        top = top.next;
        return;
    }

    public int top() {
        return top == null ? 0 : top.val;
    }

    public int getMin() {
        return top == null ? 0 : top.min;
    }
}

class Node {
    int val;
    int min;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}