155. 最小栈#

今天我们来深入探讨一道非常精彩的数据结构设计题 - LeetCode 155「最小栈」。这道题不仅考察了栈的基本操作，更蕴含着优化思维的艺术。

📚 从实际场景理解#

想象你是一位股票交易员，需要随时跟踪当前持仓中的最低价格股票。每次买入新股票或卖出旧股票后，都要能立即知道组合中的最低价。这个场景就很像我们今天要解决的最小栈问题！

问题描述#

题目目标#

设计一个支持 push、pop、top 和 getMin 操作的栈，并保证每个操作都能在 O(1) 时间复杂度内完成。

示例 1#

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

text

输出： [null,null,null,null,-3,null,0,-2] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题解析#

题目要求：设计一个支持 push、pop、top 和 getMin 操作的栈数据结构：

push(x) —— 将元素 x 推入栈中
pop() —— 删除栈顶的元素
top() —— 获取栈顶元素
getMin() —— 检索栈中的最小元素

所有操作必须在 O(1) 时间复杂度内完成。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   // 返回 -3
minStack.pop();
minStack.top();      // 返回 0
minStack.getMin();   // 返回 -2

java

🤔 思维发展过程#

1. 初学者思路#

很多人的第一反应是：用一个变量记录最小值。但这种方法在pop操作后无法知道新的最小值。

2. 进阶思路#

可以在每次push时都遍历栈找最小值，但这样getMin的时间复杂度就变成了O(n)。

3. 最优思路#

使用辅助栈同步记录当前状态下的最小值，这样所有操作都能保持O(1)时间复杂度。

🚀 优雅的解决方案#

class MinStack {
    // 主栈：按正常栈语义存储所有入栈元素
    private Stack<Integer> mainStack;
    // 辅助栈：仅存“历史最小值”，栈顶始终是当前最小值
    private Stack<Integer> minStack;

    public MinStack() {
        // 初始化主栈
        mainStack = new Stack<>();
        // 初始化最小值栈
        minStack = new Stack<>();
    }

    public void push(int val) {
        // 无条件压入主栈，保持完整数据
        mainStack.push(val);
        // 如果 minStack 为空，说明是第一个元素，必须成为当前最小值
        // 或者新元素 <= 当前最小值，也要同步压入，处理重复最小值场景
        if (minStack.isEmpty() || val <= minStack.peek()) {
            // 将新的最小值（或相同最小值）记录到辅助栈
            minStack.push(val);
        }
    }

    public void pop() {
        // 若主栈栈顶正好等于当前最小值，说明最小值即将被删除
        if (mainStack.peek().equals(minStack.peek())) {
            // 同步弹出辅助栈，回退到“上一个最小值状态”
            minStack.pop();
        }
        // 最后弹出主栈栈顶元素
        mainStack.pop();
    }

    public int top() {
        // 直接返回主栈栈顶元素
        return mainStack.peek();
    }

    public int getMin() {
        // 直接返回辅助栈栈顶，即当前最小值
        return minStack.peek();
    }
}

java

📝 代码详解#

让我们深入理解这个设计的精妙之处：

1. 双栈设计#

我们使用两个栈：主栈存储所有元素，辅助栈同步维护最小值状态。这是实现O(1)时间复杂度的关键。

2. Push操作的智慧#

主栈：无条件压入新元素
辅助栈：只在新元素小于等于当前最小值时压入这样确保辅助栈顶始终是当前状态下的最小值

3. Pop操作的巧妙#

当主栈弹出的元素等于当前最小值时，辅助栈也要相应弹出，保持同步。

4. 获取最小值#

直接返回辅助栈顶元素，时间复杂度O(1)。

🎯 易错点提醒#

数值比较
- 使用equals而不是==比较Integer对象
- 考虑空栈情况的处理
辅助栈处理
- push时要用<=而不是
- pop时需要先比较再操作
边界条件
- 栈为空时的处理
- 重复元素的处理

💡 举一反三#

这种设计思想可以扩展到许多类似场景：

最大栈
- 类似实现，但维护最大值
- 适用于需要追踪最大值的场景
范围最值
- 维护滑动窗口的最值
- 股票价格跟踪系统
频率栈
- 扩展实现最频繁元素的快速访问
- 设计新闻热点排行系统

🎨 图解演示#

<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="400" fill="#f8f9fa"/>

  <!-- 标题 -->
  <text x="50" y="40" font-size="20" fill="#1976d2">最小栈的工作原理</text>

  <!-- 主栈 -->
  <g transform="translate(100,80)">
    <text x="0" y="0" font-size="16">主栈</text>
    <rect x="0" y="20" width="100" height="250" fill="none" stroke="#388e3c" stroke-width="2"/>

    <!-- 主栈元素 -->
    <g transform="translate(10,250)">
      <rect x="0" y="-40" width="80" height="30" fill="#c8e6c9"/>
      <text x="40" y="-20" text-anchor="middle">5</text>

      <rect x="0" y="-80" width="80" height="30" fill="#c8e6c9"/>
      <text x="40" y="-60" text-anchor="middle">2</text>

      <rect x="0" y="-120" width="80" height="30" fill="#c8e6c9"/>
      <text x="40" y="-100" text-anchor="middle">6</text>

      <rect x="0" y="-160" width="80" height="30" fill="#c8e6c9"/>
      <text x="40" y="-140" text-anchor="middle">1</text>
    </g>
  </g>

  <!-- 辅助栈 -->
  <g transform="translate(300,80)">
    <text x="0" y="0" font-size="16">辅助栈（最小值）</text>
    <rect x="0" y="20" width="100" height="250" fill="none" stroke="#1976d2" stroke-width="2"/>

    <!-- 辅助栈元素 -->
    <g transform="translate(10,250)">
      <rect x="0" y="-40" width="80" height="30" fill="#bbdefb"/>
      <text x="40" y="-20" text-anchor="middle">2</text>

      <rect x="0" y="-80" width="80" height="30" fill="#bbdefb"/>
      <text x="40" y="-60" text-anchor="middle">2</text>

      <rect x="0" y="-120" width="80" height="30" fill="#bbdefb"/>
      <text x="40" y="-100" text-anchor="middle">1</text>

      <rect x="0" y="-160" width="80" height="30" fill="#bbdefb"/>
      <text x="40" y="-140" text-anchor="middle">1</text>
    </g>
  </g>

  <!-- 操作说明 -->
  <g transform="translate(500,100)">
    <text x="0" y="0" font-size="14">操作过程：</text>
    <text x="0" y="30" font-size="14">1. push(1) → 两栈都入栈</text>
    <text x="0" y="60" font-size="14">2. push(6) → 主栈入栈，最小值不变</text>
    <text x="0" y="90" font-size="14">3. push(2) → 两栈都入栈（新最小值）</text>
    <text x="0" y="120" font-size="14">4. push(5) → 主栈入栈，最小值不变</text>
  </g>
</svg>

plaintext

🌟 面试技巧#

设计思路表达
- 先说明为什么需要辅助栈
- 解释如何保证O(1)时间复杂度
优化讨论
- 可以讨论空间优化的可能性
- 提到处理特殊情况的考虑
扩展思考
- 讨论如何扩展支持其他操作
- 考虑并发场景的实现

🎩 空间优化版本#

如果对空间要求严格，我们可以在辅助栈中只存储差值：

class MinStack {
    // 差值栈：不直接存原值，而是存“当前值 - 当前最小值”
    private Stack<Long> stack;
    // 记录当前栈中的最小值
    private long min;

    public MinStack() {
        // 初始化差值栈
        stack = new Stack<>();
    }

    public void push(int val) {
        // 栈为空时，当前值就是最小值
        if (stack.isEmpty()) {
            // 第一个元素与 min 的差值定义为 0
            stack.push(0L);
            // 初始化当前最小值
            min = val;
        } else {
            // 记录新值相对当前 min 的差值（可能为负）
            stack.push(val - min);
            // 若新值更小，更新 min
            if (val < min) min = val;
        }
    }

    public void pop() {
        // 取出栈顶差值
        long diff = stack.pop();
        // diff < 0 表示该元素入栈时触发过 min 更新（它本身是新的最小值）
        if (diff < 0) {
            // 恢复删除该元素前的最小值：oldMin = currentMin - diff
            min = min - diff;
        }
    }

    public int top() {
        // 查看栈顶差值（不弹出）
        long diff = stack.peek();
        // diff < 0 时，栈顶元素就是当前 min；否则是 min + diff
        return diff < 0 ? (int)min : (int)(diff + min);
    }

    public int getMin() {
        // 当前最小值始终由 min 变量维护
        return (int)min;
    }
}

java

这个优化版本通过存储差值而不是实际值，在某些情况下可以节省空间，但需要注意处理整数溢出的问题。

这道题展示了如何通过巧妙的数据结构设计来实现高效的功能。理解这种设计思想对于解决其他数据结构设计问题也很有帮助。如果你对这个设计还有任何疑问，欢迎在评论区讨论！