LeetCode 155. 最小栈

约 4 分钟
文章信息 22 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 百度 网易 快手 蚂蚁 滴滴 携程 虾皮
标签
栈 设计

题目描述

✅ 155. 最小栈

image-20260928194353087

image-20260928194353088

题意分析

实现一个栈，除 push 入栈、pop 出栈、top 读取栈顶之外，还要用常数时间读取当前栈中的最小值。查询最小值不能删除元素，也不能每次遍历整个栈；题目保证出栈和读取操作只会在非空栈上调用。

只保存一个最小值变量不够：压入更小值时容易更新，但当这个最小值被弹出后，还需要知道剩余元素原来的最小值。栈只从顶部增删，因此可以在每一层同时记录对应的最小值，出栈时直接恢复上一层状态。

解法：主栈 + 同步最小栈

核心思路

[!blue]

使用主栈 stack 保存实际元素，辅助栈 minStack 保存最小值记录，两者始终等高。辅助栈某一层记录的是主栈从栈底到这一层的最小值，因此辅助栈顶恰好对应当前整个栈的最小值。

压入 val 时，旧元素之间的最小值已经在辅助栈顶，新栈的最小值只可能是旧最小值或 val，所以压入二者的较小值。如果辅助栈为空，说明这是第一层，直接将 val 作为最小值记录。

每次入栈都必须产生一条记录，即使新值大于或等于旧最小值也一样。这样重复出现的最小值在不同层都有自己的记录，弹出其中一个不会让另一个的最小值信息消失。

出栈时同时弹出两个栈的顶部。主栈恢复为之前的前缀，辅助栈也正好露出这个前缀当时保存的最小值，不需要重新计算。于是 top 读取主栈顶，getMin 读取辅助栈顶，所有操作都只涉及栈顶。

解题步骤

  1. 初始化主栈 stack 和辅助栈 minStack。
  2. push(val)：把 val 压入主栈，并把它与旧最小值中的较小者压入辅助栈；空栈的第一条最小值记录就是 val。
  3. pop()：同步弹出两个栈的栈顶，回到上一层状态。
  4. top() 返回主栈顶，getMin() 返回辅助栈顶，都不修改栈。

代码实现

class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> minStack = new ArrayDeque<>();

    public MinStack() {}

    public void push(int val) {
        stack.push(val);
        // 每一层保存该前缀的最小值，相等最小值也占一层。
        minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    }

    public void pop() {
        // 主栈与最小栈同步弹出，恢复上一层状态。
        stack.pop();
        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) {
    minimum := val
    if len(s.minStack) > 0 && s.minStack[len(s.minStack)-1] < minimum {
        minimum = s.minStack[len(s.minStack)-1]
    }

    s.stack = append(s.stack, val)
    // 每一层保存该前缀的最小值，相等最小值也占一层。
    s.minStack = append(s.minStack, minimum)
}

func (s *MinStack) Pop() {
    // 主栈与最小栈同步弹出，恢复上一层状态。
    s.stack = s.stack[:len(s.stack)-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]
}

复杂度分析

  • 时间复杂度：pop、top、getMin 为 $O(1)$；本实现的 push 为摊还 $O(1)$，底层动态数组偶尔扩容时会复制已有元素。
  • 空间复杂度：$O(n)$，n 为栈最多同时保存的元素数量，主栈和辅助栈各需要线性空间。

关键点总结

[!green]

  • 辅助栈顶始终是当前主栈的最小值。
  • 每次入栈都记录最小值，重复最小值也能正确回退。
  • 两个栈必须始终保持相同高度。

易错点总结

[!yellow]

  • 只维护一个最小值变量，弹出最小元素后无法恢复上一个最小值。
  • pop 时只弹主栈，会让两个栈的状态错位。
  • 辅助栈首次入栈时没有旧最小值，应直接压入 val。
  • top 读取主栈，getMin 才读取辅助栈。

相似题目

题目 难度 关联与区别
716. 最大栈 困难 同样在栈操作中维护极值，原题还支持删除最大值，需要更复杂的定位与连接。
补充题 126. 支持最大值和最小值查询的栈 中等 都在入栈时保存此前的极值以便常数时间查询；补充题同时维护最大值和最小值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/87592375
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！