LeetCode每日一题 155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

来源：力扣（LeetCode）
链接

题目分析：
1.设计一个栈，能O(1)获取奥最小元素，min需要存取变化情况。
2.个人理解，最好不要用栈的方式。

解法分析：
常规解法：用两个栈，一个正常栈，另一个存最小值，同步操作。
or一个栈，压两次出两次top取geek，min 取 geek-1。
or两个栈，一个正常栈，另一个当出现<=存取，正常栈出栈，最小值等于geek时出栈。

我最喜欢的解法：

class MinStack {
/** initialize your data structure here. */
    private class Node {
        int min;
        int val;
        Node next;
        private Node(int val, int min) {
            this(val, min, null);
        }
        private Node(int val, int min, Node node) {
            this.val = val;
            this.min = min;
            this.next = node;
        }
    }
    private Node head;
    public MinStack() {    }
    public void push(int x) {
        if (head == null) {
            head = new Node(x,x);
        } else {
            head = new Node(x,Math.min(x,head.min),head);
        }
    }
    public void pop() {
        head = head.next;
    }
    public int top() {
        return head.val;
    }
    public int getMin() {
        return head.min;
    }
}
/** * Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/