原题出处:https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnkq37/

解法一:

class MinStack {

    private ListNode listNode;

    public MinStack() {

    }
    
    public void push(int val) {
        if (listNode == null) {
            listNode = new ListNode(val,val,null);
            return;
        }
        int min = Math.min(val,listNode.min);
        listNode = new ListNode(val,min,listNode);
    }
    
    public void pop() {
        listNode = listNode.next;
    }
    
    public int top() {
        return listNode.val;
    }
    
    public int getMin() {
        return listNode.min;
    }
}

class ListNode {
    int val;
    int min;
    ListNode next;

    public ListNode(int val,int min,ListNode next) {
        this.val = val;
        this.min = min;
        this.next = next;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

思路:定义一个自定义的链表,栈的特点是"先进后出",那么我们只需要每次将链表的新节点作为链表的头结点.并在每一次入栈的时候记录当前的最小值.出栈将头结点的引用指向下一个节点即可.获取顶部数据和获取最小值,使用头节点记录的数据即可.

解法二:

class MinStack {
    // 第一个记录栈的数据
    Stack<Integer> stack1 = new Stack();
    // 第二个栈记录栈的最小值
    Stack<Integer> stack2 = new Stack();

    public MinStack() {

    }
    
    public void push(int val) {
        stack1.push(val);
        // 如果第二个栈中的数据为空或者入栈的值要小于当前的最小值,就将当前入栈的值入栈到第二个栈中
        if (stack2.empty() || val <= getMin()) {
            stack2.push(val);
        }
    }
    
    public void pop() {
        // 将第一个栈中的数据出栈,并比较当前的最小值,如果当前的最小值等于当前出栈的数据,就将当前第二个记录最小值得栈进行出栈
        if (stack1.pop() == getMin()) {
            stack2.pop();
        }
    }
    
    public int top() {
        // 获取第一个记录数据的栈顶元素
        return stack1.peek();
    }
    
    public int getMin() {
        // 获取第二个记录最小值得栈顶元素
        return stack2.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

思路:使用官方提供的Stack,我们使用两个栈分别记录当前的入栈元素和当前 入栈元素中的最小值.每一次出入栈都操作这两个定义的栈数据即可.