题目：

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

LeetCode--Min Stack

题目：

解决方案一：

ps：方案一的疑惑

博文里的分析：

方案二（效率较高，容易理解）：