LeetCode 面试题 03.02. 栈的最小值

约 4 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 程序员面试金典（第 6 版） 字节
标签
栈 设计

题目描述

✅ 面试题 03.02. 栈的最小值

image-20260929105644522

题意分析

实现入栈、出栈、查看栈顶和获取最小值。查询最小值不能每次扫描整个栈；更关键的是，最小元素弹出后，还要知道剩余元素中的最小值，因此需要保存最小值的变化历史。

解法：双栈（数据栈 + 最小栈）

核心思路

[!blue]
数据栈保存全部元素，最小栈保存尚未被弹出的最小值记录。 压入 val 时，若最小栈为空或 val 不大于当前最小值，就同时压入最小栈；若 val 更大，原最小值仍有效，无需增加记录。因此数据栈非空时，最小栈顶始终等于当前最小值。

出栈时，用刚弹出的值与最小栈顶比较。若不相等，删除的不是当前最小值，最小栈保持不动；若相等，就同步弹出一份记录，露出的上一条记录恰好是删除该元素后的最小值。后压入的更小元素一定先弹出，因而历史记录的恢复顺序与数据栈一致。

相等的最小值也要重复登记。每个相等元素各对应一条记录，弹出其中一个只删除一份，栈里剩下的同值元素仍有记录。最小栈不能只保存严格下降的值，否则会过早丢失仍然存在的最小值；也不应拿 0 等固定数值初始化，以免限制合法元素范围。

解题步骤

  1. 创建空的数据栈和最小栈。
  2. push 总是把新值压入数据栈；最小栈为空或新值不大于其栈顶时，再登记一份最小值。
  3. pop 先得到实际删除的值，若等于最小栈顶，就同步删除一份记录。最后一个数据元素弹出时，对应的最小值记录也会被移除。
  4. top 和 getMin 分别读取数据栈顶、最小栈顶，均不删除元素。后续再次向空栈压入时，会重新建立最小值记录。

代码实现

class MinStack {

    private Deque<Integer> stack;
    private Deque<Integer> minStack;

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(int val) {
        stack.push(val);

        // 相等的最小值也登记一份，弹出时才能逐份恢复。
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();

        // 根据刚弹出的值判断，最小值记录与数据元素同步删除。
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{}
}

func (s *MinStack) Push(val int) {
    s.stack = append(s.stack, val)
    // 相等的最小值也登记一份，弹出时才能逐份恢复。
    if len(s.minStack) == 0 || val <= s.minStack[len(s.minStack)-1] {
        s.minStack = append(s.minStack, val)
    }
}

func (s *MinStack) Pop() {
    top := s.stack[len(s.stack)-1]
    s.stack = s.stack[:len(s.stack)-1]
    // 根据刚弹出的值判断，最小值记录与数据元素同步删除。
    if top == s.minStack[len(s.minStack)-1] {
        s.minStack = s.minStack[:len(s.minStack)-1]
    }
}

func (s *MinStack) Top() int {
    return s.stack[len(s.stack)-1]
}

func (s *MinStack) GetMin() int {
    return s.minStack[len(s.minStack)-1]
}

复杂度分析

  • 时间复杂度：push 均摊 $O(1)$，其余操作 $O(1)$，包含底层可增长容器的扩容影响。
  • 空间复杂度：$O(H+1)$，H 为历史最大栈规模，底层容器弹出元素后不一定缩小容量。

关键点总结

[!green]

  • 最小值历史与当前仍在栈中的元素同步。
  • 相等也进入最小栈，保留重复值份数。
  • 查询只读栈顶，不重新扫描全部元素。

易错点总结

[!yellow]

  • 压最小栈只用严格小于：重复最小值缺少对应记录。
  • 弹出后拿新的数据栈顶作比较：比较对象不是刚删除的元素。
  • 只保存一个最小值变量：无法恢复被弹出最小值之前的状态。
  • top 使用 pop：查询操作错误地删除了元素。

相似题目

题目 难度 关联与区别
716. 最大栈 困难 同样在栈操作中维护极值，原题还支持删除最大值，需要更复杂的定位与连接。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/38724283
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！