Java 中使用 LinkedList 的堆栈实现

Question

我在 Leetcode 上看到了这个使用链表实现堆栈的解决方案，我几乎理解了它背后的所有逻辑，除了 min 部分。谁能解释一下代码是如何在弹出第一个最小元素后继续跟踪最小元素的？

代码

class MinStack {
    private Node head;
        
    public void push(int x) {
        if (head == null) 
            head = new Node(x, x, null);
        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;
    }
        
    private class Node {
        int val;
        int min;
        Node next;
            
        private Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

Answer 1

当你将一个新节点压入栈头时，新的最小值要么是新节点，要么是前一个最小值，它存储在前一个头中。当你弹出头部时，它会恢复到之前的最小值，存储在前一个头部中。因为 getMin() 总是看当前的头，所以这给出了正确的结果。

尝试逐步完成一些示例：

从空堆栈开始
push 5 -> 用一个节点堆叠 val = 5, min = 5, next = null

（以后我会用缩写(val, min, next)，比如(5, 5, null)）
推送 10 -> 有两个节点堆叠 (10, 5, (5, 5, null))
推送 1 -> (1, 1, (10, 5, (5, 5, null)))
pop -> 回到 (10, 5, (5, 5, null))
pop -> 回到 (5, 5, null)

Java 中使用 LinkedList 的堆栈实现

Stack implementation using LinkedList in Java

java

linked-list

stack