力扣（最小栈）-EW帮帮网

解析 LeetCode 155. 最小栈：基于链表的高效实现

一、题目分析

在这里插入图片描述

（一）功能需求

实现 MinStack 类，包含以下操作：

MinStack()：初始化栈对象。
void push(int val)：将元素压入栈。
void pop()：移除栈顶元素。
int top()：获取栈顶元素的值。
int getMin()：获取栈中的最小元素，要求时间复杂度为 O(1) 。

（二）核心挑战

如何在执行常规栈操作的同时，高效维护最小元素。若每次调用 getMin 都遍历栈查找，时间复杂度会达到 O(n) ，无法满足题目要求。因此，需在栈的结构设计上做文章，让最小元素的获取无需遍历。

二、算法思想：链表节点存储“值 + 当前最小值”

（一）链表节点的设计

使用自定义的 Node 类，每个节点存储三个信息：

val：当前节点存储的元素值。
min：以当前节点为栈顶时，栈中的最小元素值。
next：指向下一个节点的指针（构建链表结构）。

这样，每个节点在入栈时，就记录了从栈底到当前节点的最小元素，后续获取最小元素时，直接访问栈顶节点的 min 属性即可，时间复杂度为 O(1) 。

（二）栈的操作逻辑

初始化：用一个哨兵节点（head ）简化链表操作，其 val 可设为任意值（如示例中的 666 ），min 设为 Integer.MAX_VALUE（不影响实际逻辑），next 初始为 null 。
push 操作：创建新节点时，计算当前的最小元素（比较当前值 val 和前一个节点的 min 值），将新节点插入链表头部（head.next 指向新节点）。
pop 操作：直接将 head.next 指向下下个节点，移除栈顶（链表头节点）。
top 操作：返回 head.next.val ，即链表头节点的值。
getMin 操作：返回 head.next.min ，即链表头节点记录的当前栈最小元素。

三、代码实现与详细注释

class MinStack {
    // 自定义链表节点类，存储值、当前最小值、下一个节点
    static class Node {
        Node next = null;
        int val;
        int min;
        Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
    Node head; // 链表头节点，作为哨兵节点
    // 初始化栈，创建哨兵节点
    public MinStack() {
        // 哨兵节点val设为666（无实际意义），min设为Integer.MAX_VALUE
        head = new Node(666, Integer.MAX_VALUE, null); 
    }
    // 压栈操作
    public void push(int val) {
        // 计算新节点的min：前一个节点（head.next）的min（若存在）与当前val的较小值
        int currentMin = (head.next != null) ? head.next.min : head.min; 
        currentMin = Math.min(currentMin, val);
        // 新节点插入链表头部（head.next指向新节点）
        Node newNode = new Node(val, currentMin, head.next); 
        head.next = newNode;
    }
    // 弹栈操作：移除链表头节点（栈顶）
    public void pop() {
        if (head.next != null) { // 确保栈非空（实际使用中需处理空栈情况，题目测试用例保证合法操作）
            head.next = head.next.next; 
        }
    }
    // 获取栈顶元素值
    public int top() {
        return head.next.val; // 链表头节点的val即为栈顶值
    }
    // 获取当前栈的最小元素
    public int getMin() {
        return head.next.min; // 链表头节点的min即为当前栈最小元素
    }
}

（一）代码流程拆解

初始化：创建 head 哨兵节点，其 min 设为 Integer.MAX_VALUE ，后续节点入栈时会动态计算真实的最小元素。
push 操作：
- 计算当前新节点的 min 值：若链表已有节点（head.next != null ），则取 val 和前一个节点 min 的较小值；若链表为空（初始状态），则 val 就是当前最小。
- 将新节点插入链表头部（head.next 指向新节点），保证栈顶始终是链表头节点。
pop 操作：直接跳过链表头节点（head.next = head.next.next ），实现栈顶元素的移除。
top 操作：返回链表头节点的 val 属性，即栈顶元素值。
getMin 操作：返回链表头节点的 min 属性，即当前栈的最小元素，无需遍历，时间复杂度 O(1) 。

（二）关键逻辑解析

哨兵节点的作用：简化链表操作，避免处理 head.next == null 的边界情况（如初始化时直接操作 head.next ）。
节点 min 属性的维护：每个节点在入栈时，主动记录当前栈的最小元素，使得 getMin 操作只需访问栈顶节点的 min 属性，保证了时间复杂度 O(1) 。
链表结构的优势：栈的 push 和 pop 操作对应链表的头部插入和删除，时间复杂度均为 O(1) ，同时天然维护了栈的“后进先出”特性。

四、复杂度分析

（一）时间复杂度

push：O(1) 。创建新节点并插入链表头部，操作时间固定。
pop：O(1) 。只需修改链表指针，操作时间固定。
top：O(1) 。直接访问链表头节点的 val 属性。
getMin：O(1) 。直接访问链表头节点的 min 属性。

所有操作的时间复杂度均为 O(1) ，满足题目要求。

（二）空间复杂度

每个元素入栈时，需存储一个 Node 对象，包含 val、min、next 。空间复杂度为 O(n) ，n 为栈中元素的最大数量。

力扣（最小栈）