Leetcode 155. 最小栈（Medium）

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

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

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

思路：本来想用hashMap来模拟栈，储存一个列表长度值，key是index，value是值，然后因为最小值不一成不变的，有删除的出现，而且还要求O(1)，就必须使用链表，别无他法。使用hashmap的话，就要再建立一个Node列表就会导致不太清晰。所以最终直接使用Stack<Node>，栈和列表共存，然后建立一个Head头节点方便链表的操作。（细节也就节点删除不要为空，做一下判断；还有可以把删除的元素的指针断掉，让他回收掉）。代码如下：

class MinStack {
    
    class Node {
        int val;
        Node next;
        Node pre;
        public Node(int val, Node sortPre, Node sortNext) {
            this.val = val;
            this.pre = sortPre;
            this.next = sortNext;
        }
        public Node() {
        }
    }
    Node head = new Node();
    private Stack<Node> stack = new Stack<>();

    public MinStack() {
    }
    
    public void push(int val) {
        Node newNode;
        if(stack.empty()) {
            // 如果栈为空，就创建一个没有前后指针的节点
            newNode = new Node(val, head, null);
            head.next = newNode;
        } else {
            newNode = new Node(val, null, null);
            // 从头节点开始遍历找到合适的位置插入
            Node cur = head.next;
            while(cur != null) {
                // 比较大小
                if (cur.val >= newNode.val) {
                    newNode.next = cur;
                    newNode.pre = cur.pre;
                    cur.pre.next = newNode;
                    cur.pre = newNode;
                    break;
                }
                cur = cur.next;
            }
        }
        stack.push(newNode);
        
    }
    
    public void pop() {
        Node pop = stack.pop();
        
        for(Node i = head.next; i != null; i = i.next) {
            if (i.val == pop.val) {
                // 就需要移除掉这个节点
                i.pre.next = i.next;
                if (i.next != null) i.next.pre = i.pre;
                i.pre = null;
                i.next = null;
            }
        }

    }
    
    public int top() {
        return stack.peek().val;
    }
    
    public int getMin() {
        return head.next.val;
    }
}