【LeetCode 155】—最小栈 - 详解与实现

坚持用 清晰易懂的图解 + 代码语言，让每个知识点变得简单！
🚀呆头个人主页详情
🌱 呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭： “不患无位，患所以立。”

摘要

🚀 你好，欢迎来到《编程闯关记》！
这里是算法与数据结构的实战基地，也是你从“暴力解法”到“最优解”的进化场。

🔍 专栏初衷：

• 用清晰的图解 + 多语言代码（Python/Java/C++/C），拆解每道题背后的逻辑。
• 不只讲“怎么做”，更讲“为什么”——从题目分析、边界条件到复杂度优化。
• 适合想夯实基础或突击面试的你，尤其针对LeetCode/牛客高频题！

💡 如何使用本专栏：
1️⃣ 先独立思考：尝试自己写出第一版代码（哪怕很烂）。
2️⃣ 对比解法：看看我的思路和你的差异，吸收优化技巧。
3️⃣ 举一反三：每篇末尾会附相似题目链接，趁热打铁。

📌 坚持打卡：
算法没有捷径，但正确的方法能让你少走弯路。每天15分钟，和我一起用代码雕刻思维！

（正文开始👇）

目录

题目描述

力扣链接直达----------请点击

设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象
• void push(int val) 将元素val推入堆栈
• void pop() 删除堆栈顶部的元素
• int top() 获取堆栈顶部的元素
• int getMin() 检索堆栈中的最小元素

解题思路

这道题的关键在于如何在常数时间内获取栈中的最小元素。普通栈只能访问栈顶元素，要获取最小值需要遍历整个栈，时间复杂度为O(n)。

为了实现O(1)时间获取最小值，我们可以使用辅助栈的方法：

1. 使用两个栈：一个普通栈存储所有元素，一个最小栈只存储当前最小值
2. 当有新元素入栈时，将其与最小栈顶元素比较，如果更小则也入最小栈
3. 当出栈时，如果出栈元素等于最小栈顶元素，则最小栈也要出栈

这样，最小栈的栈顶元素始终是当前栈中的最小值。

代码实现

#include <stack>
#include <stdexcept>
using namespace std;

// 最小栈的实现：普通栈 + 辅助栈
class MinStack {
public:
    MinStack() {}

    // 压栈操作
    void push(int val) {
        _st.push(val);  
        // 如果辅助栈为空，或者新值不大于当前最小值，则同步压入辅助栈
        if (_minst.empty() || val <= _minst.top()) {
            _minst.push(val);
        }
    }

    // 出栈操作
    void pop() {
        if (_st.empty()) return;  // 防御：空栈直接返回
        if (_st.top() == _minst.top()) {
            _minst.pop();        // 若栈顶是最小值，辅助栈同步出栈
        }
        _st.pop();               // 普通栈出栈
    }

    // 获取栈顶
    int top() {
        if (_st.empty()) throw runtime_error("stack is empty");
        return _st.top();
    }

    // 获取最小值
    int getMin() {
        if (_minst.empty()) throw runtime_error("min stack is empty");
        return _minst.top();
    }

private:
    stack<int> _st;     // 普通栈：存所有元素
    stack<int> _minst;  // 辅助栈：只存最小值
};

代码分析

1. 数据结构：

   • _st：普通栈，用于存储所有入栈的元素
   • _minst：最小栈，只存储可能成为最小值的元素

2. push操作：

   • 将元素压入普通栈
   • 如果最小栈为空或新元素小于等于最小栈顶元素，则将新元素也压入最小栈

3. pop操作：

   • 如果普通栈顶元素等于最小栈顶元素，说明当前最小值要被弹出，最小栈也要弹出
   • 普通栈正常弹出元素

4. top操作：

   • 直接返回普通栈的栈顶元素

5. getMin操作：

   • 直接返回最小栈的栈顶元素，即为当前栈中的最小值

复杂度分析

• 时间复杂度：所有操作均为 O(1)
• 空间复杂度：O(n)，最坏情况下，最小栈也需要存储所有元素

总结

这道题是栈的经典应用题，通过辅助栈的方式实现了O(1)时间获取最小值的功能。关键点在于理解何时将元素压入最小栈，以及何时从最小栈弹出元素。这种双栈设计是解决此类问题的常用技巧。