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

我不是呆头

发布于 2025-12-20 13:18:40

940

摘要

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

用清晰的图解 + 多语言代码（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)时间获取最小值，我们可以使用辅助栈的方法：

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

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

代码实现

#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;  // 辅助栈：只存最小值
};