题目

• 概述：设计一个栈，除了支持栈的核心操作push(x)，pop()，top()外，还支持在常数时间内找到栈中最小的元素

1. push(x)：将x入栈
2. pop()：将栈顶元素出栈
3. top()：获取栈顶元素
4. getMin()：取得栈中最小元素

出处：https://leetcode-cn.com/problems/min-stack/

思路

• 为栈中每一个结点添加一个属性minValue，标志以该结点为栈顶的栈的最小元素

• 每次入栈的结点的minValue为该结点的值本身

• 入栈时比较入栈的结点和栈顶结点的minValue，若入栈的结点的minValue大于栈顶结点的minValue，则更新入栈的结点的minValue为栈顶结点的minValue

注意：如果栈中没有元素，则直接入栈即可

• 栈中最小元素为栈顶元素的minValue

代码

class MinStack {
    private Node dummyHead;
    
    /** initialize your data structure here. */
    public MinStack() {
        dummyHead = new Node(0);
    }
    
    public void push(int x) {
        Node newNode = new Node(x);
        if (dummyHead.next != null) {
            if (newNode.minValue > getMin()) {
                newNode.minValue = getMin();
            }
        }
        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
    }
    
    public void pop() {
        Node delNode = dummyHead.next;
        dummyHead.next = delNode.next;
        delNode.next = null;
        delNode = null;
    }
    
    public int top() {
        return dummyHead.next.value;
    }
    
    public int getMin() {
        return dummyHead.next.minValue;
    }
    
    class Node {
        int value;
        Node next;
        int minValue;
        public Node(int value) {
            this.value = value;
            this.next = null;
            this.minValue = value;
        }
    }
}