请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

方法一：双栈的实现

    class MinStack_2 {Stack<Integer> stack;Stack<Integer> minStack;/*** initialize your data structure here.*/public MinStack_2() {stack = new Stack<>();minStack = new Stack<>();}public void push(int x) {stack.push(x);if (minStack.isEmpty()) {minStack.push(x);return;}int peekNum = minStack.peek();if (peekNum < x) {minStack.push(peekNum);return;}minStack.push(x);}public void pop() {stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}}

方法二：链表的实现：

    class MinStack {class Node {int val;int min;Node next;public Node(int val, int min) {this.val = val;this.min = min;}public Node(int val, int min, Node next) {this.val = val;this.min = min;this.next = next;}}Node head;/*** initialize your data structure here.*/public MinStack() {}public void push(int x) {if (head == null) {head = new Node(x, x);return;}int min = Math.min(head.min, x);head = new Node(x, min, head);}public void pop() {head = head.next;}public int top() {return head.val;}public int getMin() {return head.min;}}